For instance you are given an array [3,5,8,10,6,12,4]. You are to find the largest possible increase between two pairs of element i and j where j > i.
In the above case the answer would return 9 -> 12 - 3 = 9.
So i though of the obvious solution which is O(N^2). Here is my code
public class Max {
public static void main(String[] args) {
int[] array = {3,5,8,10,6,12,4};
System.out.println(getMax(array));
}
public static int getMax(int [] arr)
{
int maxVal = 0;
for(int i = arr.length-1; i>0; i--)
{
for(int j = 0; j<i; j++)
{
if(arr[i]-arr[j] > maxVal)
{
maxVal = arr[i] - arr[j];
}
}
}
return maxVal;
}
}
However i was wondering if it is possible to improve the solution to O(NlogN) because what if we use divide and conquer approach? Can someone guide me ?
UPDATE I simply can't find the max and min because the index of j has to be greater than index i. If i simply just look for the max and min value then i might get a case where index i is greater than index j and that is not allowed.
Keep the minimum so far and update accordingly:
min = array[0]
max_diff = 0
for each element e, starting from the second:
if e - min > max_diff:
max_diff = e - min
if e < min:
min = e
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments