Longest Increasing Subsequence - Medium - NL
Published:
Question
- https://leetcode.com/problems/longest-increasing-subsequence/
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Approach
- DP
Solution
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
if(n==0){
return 0;
}
int dp[n];
for(int i=0;i<n;i++){
dp[i]=1;
}
int max_ans=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=max(dp[i],1+dp[j]);
}
}
if(max_ans<dp[i]){
max_ans=dp[i];
}
}
return max_ans;
}
};