I tried LIS…but something wrong in my code…Please tell me what is the wrong in my code ?
Can you explain your code. What is n and what is p?
Can you please specify the problem statement.
Longest Increasing Subsequent.
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);
}