There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: O(N) solution
S = a[i] - a[j] where i>j
and
S > 0
/**
* There is an integer array consisting positive and negative integers. Find
* maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0
*/
public class MaxPositiveDifference {
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, -9, 4, 5, 6 };
maxDifference(a, 8);
}
public static void maxDifference(int a[], int size) {
int min = 0;
int maxDiff = 0;
for (int i = 0; i < size; i++) {
if (a[i] < a[min])
min = i;
int diff = a[i] - a[min];
if (diff > maxDiff) {
maxDiff = diff;
}
}
System.out.println("maximum differene in the array : " + maxDiff);
}
}
Refer : http://www.geeksforgeeks.org/archives/6463
Similar question : find the the maximum difference of two numbers in an array
ReplyDeleteSorting takes O (N logN) .. You can find the minimum and the maximum in a single traversal i.e O(N) time and return the difference of the two ..
To find minimum and maximum you can do the following :
i) Assign min = max = first element in the array.
ii)Then traverse the array .. for each element in the array .. if it is greater than max , update max = that element .. else if it is lesser than min, update min as that element ..
After finding min and max return the difference of the two
http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-in-union-of.html
ReplyDelete