Longest increasing subsequence(LIS) in O(n^2) 🚩
Mon Jan 24 2022 14:07:42 GMT+0000 (Coordinated Universal Time)
Saved by
@vaibhav_55
// This is a pure dynamic programing approach which takes O(n^2) time
int LIS(vector<int> &ar, int n)
{
int dp[n]; // creating dp array
int ans = dp[0] = 1;
for (int i = 1; i < n; i++)
{
int maxi = 0;
// traversing for all previous elements
for (int j = 0; j < i; j++)
{
if (ar[i] > ar[j])
{
maxi = max(maxi, dp[j]);
}
dp[i] = 1 + maxi;
// here answer is the largest value from dp array
ans = max(ans, dp[i]);
}
}
return ans;
}
content_copyCOPY
Comments