Practice- LIS

1

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

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;
}
3

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