 # What is the wrong in this code?

I tried LIS…but something wrong in my code…Please tell me what is the wrong in my code ?

You can use Dynamic Programming to solve this problem efficiently.
My solution for LIS with comments and explaination

//Author Abhishek Kumar
#include<bits/stdc++.h>
#define vi vector
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vpi vector
#define MAX (int)1e5
#define big (int)1e9+7
#define ll long long
#define si set
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define f first
#define s second
#define rep(i,a,b) for(int i=a;i<b;i++)
#define reps(i,a,b) for(int i=a;i<=b;i++)
#define ull unsigned long long
using namespace std;

//Longest Increasing subsequence

//Linear DP solution

//Recurrence

//dp[i]=Longest Increasing subsequence ending at index i

//Thus dp[i]=1+max(dp[j]) for all j from 1 to i such that a[i]<=a[j]

// =1 is no such j exists

//Time Complexity O(n^2)

//Space Complexity O(n)

int lis(int *a,int n)
{
int dp[n];

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

int w=0;
for(int j=0;j<i;j++)
{

``````        if(a[j]<=a[i])

w=max(w,dp[j]);
}
``````

dp[i]=1+w;
}

return dp[n-1];
}
int main()
{
int n;

cin>>n;

int *a=new int[n];

rep(i,0,n)

cin>>a[i];

cout<<lis(a,n);

}

1 Like

Can you explain your code. What is n and what is p?

Can you please specify the problem statement.

Longest Increasing Subsequent.

@mathecodician, here n=0 index and p is the number of elements.

Tnq @inovation123.