### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

This was one of the simple problems of this month. A lot of you were able to solve it easily. The constraints of the problem were such that only O(n) solution could pass. The problem could be stated simply as: Find 2 numbers ai and aj such that aj-ai is maximum. (1 <= i < j <= N) A couple of approaches to this problem: Approach 1: Store the numbers in an array a. Take 2 additional arrays b & c. b[i]=maximum over all ax (for all x such that i<=x<=n) c[i]=minimum over all ax (for all x such that 1<=x<=i) Both these arrays can be computed in O(n) time and space. Clearly, answer will be max(b[i]-c[i]) for all i. This can be found in O(n) too. Approach 2: Take a variable âminmâ which denotes the minimum value encountered so far. Let âansâ denote the maximum difference achieved so far. Read the numbers one by one. Let current value be cur. ans=max(ans,cur-minm) minm=min(minm,cur); Finally, the answer would be in âansâ.

### SETTERâS SOLUTION

Can be found here.

### TESTERâS SOLUTION

Can be found here.