Skip to content

Instantly share code, notes, and snippets.

@vivan188
Created March 19, 2021 11:50
Show Gist options
  • Save vivan188/3549b6288429b42469c4fb0fea6820cb to your computer and use it in GitHub Desktop.
Save vivan188/3549b6288429b42469c4fb0fea6820cb to your computer and use it in GitHub Desktop.
LIS_DP
int longest_increasing_subsequence(int arr[], int N)
{
int lis[N]
for(i = 0 to N-1)
lis[i] = 0
lis[0] = 1
for(i = 1 to N-1)
{
for(j = 0 to i-1)
{
if(arr[j] < arr[i])
lis[i] = max(lis[i], lis[j] + 1)
}
}
int ans = 1
for(i = 0 to N-1)
ans = max(ans, lis[i])
return ans
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment