Question: 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
Answer:
An inefficient solution to this problem is that we can traverse the array from the start run a loop for each element and then check for all other number which are coming later in array traversal. But this will be a very inefficient solution and will have runtime O(n^2).
A better solution is that we can calculate the max difference (glbdiff) for the subarray traversed till now and whenever we find a better difference value we can replace glbdiff by this value (locdiff). This is a dynamic approach and complete in O(1) space and O(n) time.
Code:
#include<iostream>
using namespace std;
int main()
{
int locdiff, loci, locj, glbdiff, glbi, glbj, i,n;
int in[100]={0,};
glbi= glbj=glbdiff= 0;
cin >> n;
for (i=0; i<n; i++)
cin >> in[i];
loci = 0; locj=1;
locdiff = in[locj] - in[loci];
for (i=2; i<n; i++)
{
if (in[i] < in[loci])
{
loci = i;
locj= i+1;
locdiff = in[locj] - in[loci];
if(locdiff > glbdiff)
{
glbi = loci;
glbj = locj;
glbdiff = locdiff;
}
}
else
{
locj = i;
locdiff = in[locj] - in[loci];
if(locdiff > glbdiff)
{
glbi = loci;
glbj = locj;
glbdiff = locdiff;
}
}
}
cout << "i = " << glbi << " j = " << glbj << " diff = " << glbdiff << endl;
}
UPDATE: A cleaner version of above code is as below:
void MaxDiff(int in[], int sz, int &start, int &end) {
int min = 0;
int maxDiff = 0;
start = end = 0;
for (int i = 0; i < sz; i++) {
if (in[i] < in[min])
min = i;
int diff = in[i] - in[min];
if (diff > maxDiff) {
start = min;
end = i;
maxDiff = diff;
}
}
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Hey,
cant we use the method to find the largest and smallest numbers in an array in 3n/2 comparisons algo and then return the difference between these two?
No we can't. please see the condition "i>j"...
What if the array sorted in descending order?
@Alyosha: That's a boundary condition. You can have a check for that.
Will get array out of bound exception/segmentation fault at line
locj= i+1; for some inputs. Try {-3, 5, 2, -2, 1, 0, -6, 7, -8};
put if (locj >= n) break; after that line.
also will not work for array size 2.
{-3, 5}
@Jishan: I am not getting any segmentation fault for {-3, 5, 2, -2, 1, 0, -6, 7, -8} Are you sure to get the input right i.e. first number of elements and then elements? Also, which compiler do you use?
I agree, it's not working for 2 elements, but that's a boundary condition and you can always write that. Idea here is the login and not considering all the boundary cases.
Hi there,
it seems it doesn't work for this case:
{ 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14 }
The correct answer should be 24, but it returns 13.
hi there,
I think the problem comes from this:
if (in[i] < in[loci]) {
loci = i;
locj= i+1;
.....
You probably should not have locj incremented.
Since the modified code still doesn't work for this case: { 56, 44, 8, 59, 120, 9, 121, -6, -10, 90, -11 };
I changed the code a little bit to:
int curri = 0, currj = 1, maxDiff = 0, maxi = 0, maxj = 0;
int currDiff = a[currj] - a[curri];
for (int i = 2; i < a.length; i++) {
if (a[i] < a[curri]) {
curri = i;
currDiff = a[maxj] - a[curri];
if (currDiff > maxDiff) {
maxi = curri;
maxDiff = currDiff;
}
} else {
currj = i;
currDiff = a[currj] - a[maxi];
if (currDiff > maxDiff) {
maxj = currj;
maxDiff = currDiff;
}
}
}
@Yuan Jin,
The question is:
S = a[i] - a[j] where i>j and S > 0
Seems you miss the condition (where i>j).
24 will be the answer if this condition is not there because in this case 'i' is less then 'j'. So for the given input 13 (14-1) is expected answer.
I think we can even do it using stacks.
int maxDifference(int a[], int n)
{
stack S;
if(n == 0)
return 0;
S.push(a[0]);
int s;
int max = -1;
int i = 1, x;
while(!S.empty())
{
if((i == n) || S.top() > a[i])
{
s = 0;
x = S.top();
S.pop();
while(!S.empty())
{
s += (x - S.top());
x = S.top();
S.pop();
}
if(s > max)
max = s;
if(i == n)
break;
}
S.push(a[i]);
i++;
}
return max;
}
The cleaner version should start its loop from 1, not from 0 (which is a completely useless iteration).
That's a very clever comment, Alyosha. However, Akash, the problem definition requires that the sum is strictly more than zero. So, simply, if the value of maxDiff in the cleaner version is still zero after we finish - just declare that there exists no such maximum difference in the input array. You don't need to check that separately.
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] array = new int[]{-3, 5, 2, -2, 1, 0, -6, 7, -8};
int[] array = new int[]{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
int len = array.length ;
int i = 1 ;
int j = 0 ;
int locdiff = 0 , glbdiff = 0;
while( i != j && j < len - 1 ){
locdiff = array[i] - array[j];
if( locdiff > glbdiff ){
glbdiff =locdiff ;
}
if( i == len - 1){
j++;
i = j+1;
}else{
i++;
}
}
System.out.println("Max difference in array :" + glbdiff );
}
why i am not able to post my complete solution here?
it eats up 2-3 lines in between
public class MaxDiffArray {
public static void main(String[] argv) {
String ns = argv[0];
String[] nss = ns.split(",");
Integer[] numbers = new Integer[nss.length];
for (int i = 0; i < nss.length; i ++) {
numbers[i] = Integer.parseInt(nss[i].trim());
}
MaxDiffArray mda = new MaxDiffArray();
System.out.println(mda.maxDiff(numbers));
}
public List maxDiff(Integer[] numbers) {
int max = numbers[0], distance = 0, prob_min = Integer.MAX_VALUE;
int min = max;
for (int i = 1; i < numbers.length; i ++) {
int n = numbers[i];
if (n < prob_min) {
prob_min = n;
}
if (n > max) {
max = n;
if (prob_min < min) {
min = prob_min;
}
distance = max - min;
} else {
//do n and prob_min have a chance together?
int new_dist = n - prob_min;
if (new_dist > distance) {
distance = new_dist;
min = prob_min;
max = n;
}
}
}
return Arrays.asList(new Integer[]{distance, min, max});
}
}