Question

Develop a divide-conquer algorithm with complexity nlogn for finding the maximum difference of a give array A= a₀,a₁, ……a_n-1, i.e finding the indices m and k, m>=0 ,k<=n-1, and m<k such that a_k- a_m is the maximum difference.

Provide a solution in Java.

Answer 1

CODE

public class Main

{

public static int maxDiff (int arr[])

{

int n = arr.length;

int diff = arr[1] - arr[0];

int curr_sum = diff;

int max_sum = curr_sum;

for(int i = 1; i < n - 1; i++)

{

diff = arr[i + 1] - arr[i];

if (curr_sum > 0)

curr_sum += diff;

else

curr_sum = diff;

if (curr_sum > max_sum)

max_sum = curr_sum;

}

return max_sum;

}

public static void main(String[] args)

{

int arr[] = {47, 64, 2, 18, 98, 12};

System.out.print("Maximum difference is " + maxDiff(arr));

}

}