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’.
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)
What does this paragraph mean?
@shubham99 Reduce the complexity of your solution. It is n^2.
As it is pointed above “The constraints of the problem were such that only O(n) solution could pass.”