# Practice- LIS

I was practicing on dp, got WA on following ques…

https://www.codechef.com/problems/PEC005
Here goes code…

``````#include <bits/stdc++.h>
#define ll long long
#define loop(a) for (ll i = 0; i < a; i++)
#define ploop(a, b, c) for (ll a = b; a < c; a++)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007
#define N 1000005
#define endl '\n'
#define codingisez ios_base::sync_with_stdio(0);
#define lovish cin.tie(0);
#define startTime clock_t tStart = clock();
#define endtime cout << "\n\nTime taken: " << (double)(clock() - tStart) / CLOCKS_PER_SEC << endl;
using namespace std;

int main()
{
codingisez lovish
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
startTime
#endif

ll t,n;
cin>>t;
while (t--)
{
cin>>n;
ll a[n];
loop(n) cin>>a[i];
ll dp[n];
loop(n) dp[i]=1;
// loop(n) cout << dp[i] << endl;

for(ll i=1;i<n;i++){
for(ll j=0;j<i;j++){
if(a[i]>a[j] && dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
}
}
// cout<<dp[i]<<endl;
}
cout<<*max_element(dp,dp+n)<<endl;
}

#ifndef ONLINE_JUDGE
endtime
#endif
return 0;
}
``````

Everything is correct except if() condition. It should be like this:-

if(a[i]>=a[j])
dp[i]=max(dp[i], dp[j]+1);

1 Like