fit to play

 So, this was one of those problems where you feel like there is no better approach possible other than what you have thought, but like most of the times, I was wrong here too, and I knew that somehow there would be a way that would be more optimal than the approach that I was using.

After taking a hell lot of thinking and analyzing the possible approaches I came to the conclusion that made a difference of 1.59 secs in the Test Cases( both the codes were in C++14).

The First Approach basically gave a TC of O(n^2) and the Second one was O(n). If you get the optimal approach in the first thought after seeing the problem statement then it would be great but even if you don't, and get a TLC, then first try thinking about the possibility, you are very close.

Even when you cannot think about any idea, then before directly going to the Explanation part see the Code because that helps a lot in building your logic and the fear of code that people possess. 

The 1st Approach took 1.66 secs.

The 2nd approach took 0.07 secs with the Optimization of syncing with stdio. 

Without the optimization of stdio, the Time Taken was 0.20 secs. That's a difference of 0.13 secs. I haven't coded this in Python bcz of the Constraints, but if I will then I will update it's Time too.

The Explanations are given below along with both the codes:-

Code Implementation- 1st Approach:-

#include <bits/stdc++.h>

using namespace std;

int main() {

    /* Previous Approach that wasn't Optimal, O(n^2) TC */

    ios_base::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t){

        int n;

        cin>>n;

       

        vector<int> goals(n);

        int m_goal=-1;

        for(int i=0;i<n;i++){

            cin>>goals[i];

            if(goals[i]>m_goal){

                m_goal=goals[i];

            }

        }

        int m_elem=-1;

        for(int i=0;i<n-1;i++){

            if(goals[i]==m_goal){

                continue;

            }

            for(int j=i+1;j<n;j++){

               

                if(goals[j]-goals[i]>m_elem){

                    m_elem=goals[j]-goals[i];

                }

            }

        }

        if(m_elem==-1){

            cout<<"UNFIT"<<endl;

        }

        else{

            cout<<m_elem<<endl;    

        }

        t--;

    }

    return 0;

}

Explanation- 1st Approach:-

The 1st Approach is just based on the logic that to get the max improvement we compare every number with all the number ahead of it. It is a very banal idea and works fine but fails the Time Limit of 1 sec as this takes 1.66 secs, whereas the 2nd approach takes 0.07 secs only, bcz in this approach we are comparing every num with all nums ahead of that num. But that's not required as mentioned in the Explanation of 2nd Approach.

Code Implementation- 2nd Approach:-

#include <bits/stdc++.h>

using namespace std;

int main() {

    /* Optimal Approach */

    ios_base::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t){

        int n;

        cin>>n;

        vector<int> arr(n);

        for(int i=0;i<n;i++)cin>>arr[i];

        if(n==1){

            cout<<"UNFIT"<<endl;

            t--;

            continue;

        }

        vector<int> maxs(n-1);

        maxs[n-2]=arr[n-1];

        int ans=maxs[n-2]-arr[n-2];

       

        // Getting the max nums

        for(int i=n-3;i>=0;i--){

            maxs[i]=max(arr[i+1],maxs[i+1]);

            if((maxs[i]-arr[i])>ans){

                ans=maxs[i]-arr[i];

            }

        }

        if(ans>0) cout<<ans<<endl;

        else cout<<"UNFIT"<<endl;

        t--;

    }

    return 0;

}

Explanation- 2nd Approach:-

This is the 2nd Approach. In this, I basically use the idea of 1st Approach just in an optimal and efficient way. Simply, instead of comparing every number with all numbers which are in front of that number, we just compare or I can say we find the difference that would be important, means the difference of the number with the max of the numbers ahead of that number, like if we have numbers like --> 1,2,4,3,2 so in this when considering 1 we don't have to compare 1 with every number ahead of it(2,4,3,2) bcz that would ultimately be of no importance, we just need to find the difference of 1 and 4, means we just have to find the max of all the numbers that are ahead of the current number and when we will find the respective differences for all the nums like this means the differences would be like--> 3,2,-1,-1, and would just find the max of these differences while initialising them only. Thatt's what has been done in this Approach. For finding the max number out of all the numbers which are present we can slice the arrays and find their max but that would not be optimal. So, we use the logic that:- We find the max of the 2nd last number, that would obviously be the last number bcz it's just 1 num and it's the max for the 2nd last elem. Now, when we consider the 3rd last num(4) then instead of considering every elem ahead of it, (like here 3 and 2) we will just compare the max that is ahead of 2nd last elem with the 2nd last elem, bcz if the max ahead of 3, that is 2, if that is less than 3 then the max ahead for 4 would be 3, and we just use this for every elem. Now we can first find max for every elem and then get the differences to find the max difference but as we are finding the max nums, so we can calculate the differences there only and if we can calculate the difference then we can also calculate the max of those differences so we don't have to loop again. That's it!