You are given an array A of size n.Give an algorithm to find i and j such that 1) i < j and 2) A[j] - A[i] is maximum among all such A[x] - A[y] where

You are given an array A of size n.Give an algorithm to find i and j such that
1) i < j and
2) A[j] - A[i] is maximum among all such A[x] - A[y] where x > y.

Intention is: given j, how to choose i in order to achieve a maximum subtraction. The answer is to choose the minimum value in A[0]..A[j-1] so that A[j]-A[i] is maximized.

int max = MIN_INT;            // max subtraction
int max_i = 0, max_j;      // max corresponding i, j
int min = A[0], min_i = 0; // min value since so far

for (int i = 1; i < n; i++) {
  if (A[i] - min > max) {
    max = A[i] - min;
    max_i = min_i;
    max_j = i;
  }
  if (A[i] < min) {
    min = A[i];
    min_i = i;
  }
}