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
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.