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;
}
}
}