# PLAYFIT - Editorial

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.

1 Like

how can the given two arrays can be computed in O(n) time complexity will u please explain it a bit more i am not in hurry to look into the solution…

Ive used same approach as Approach 1. But It is giving me TLE.

^use faster i/o methods.

easily…try it yourself.

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?

Why am I getting TLE for this solution ?

And also why is minm initialized with 100000007 ?

P.S. - I know why we get TLE in a code , I just want to know if it due to my approach or if any changes can be done to this code.

@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.”

Why kadane algorithm is giving WA in this problem? Thanks in advance.

https://www.codechef.com/viewsolution/16695987
Can anyone point out the problem in this solution.