Given an unsorted array, find the index i and j such that, j>i and (a[j] – a[i]) is maximum?

A linear time solution which I find pretty elegant:

```
private void MaxDiff(int[] a)
{
int min = a[0]; // assume first element as minimum
int maxdiff = 0;
int posi = -1, posj = -1, minpos = 0;
for (int i = 1; i < a.Length; i++)
{
if (a[i] < min)
{
min = a[i];
minpos = i;
}
else
{
int diff = a[i] - min;
if (diff > maxdiff)
{
maxdiff = diff;
posi = minpos;
posj = i;
}
}
}
System.out.format("i=%d, j=%d",posi,posj);
}
```

Advertisements