SMHTD - Editorial

PROBLEM LINK:

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Longest Increasing subsequence.

EXPLANATION

For each element of modified sequence we have bi >= i (1<=i<=n)
and we need to find the longest increasing subsequence of the original sequence ai and ai >= i.
We keep such ai unchanged and other values can be changed into the value as their index.
If we make another ci = ai - i, the answer is the equal to
(n - the longest of the non-decreasing subsequence with no negative number)
and for longest non-decreasing subsequence , a O(nlogn) solution can be used.

i was getting TLE, i was using only one loop.
i do’nt know what the problem with my code
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int count=0;
long int n;
cin>>n;
long int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int m=arr[0];
for(int i=1;i<n;i++)
{
if(arr[i]>m)
{
m=arr[i];
continue;
}
if(arr[i]<=m)
{
arr[i]=m+1;
m=arr[i];
count++;
}
}

    cout<<count<<endl;
    
}
return 0;

}