Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #300: Longest Increasing Subsequence
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n==0) {
return 0;
}
vector<int> dp(n);
dp[0] = 1;
for (int i=1; i<n; i++) { // Find the length of the longest increasing
// subsequence that ends at index i.
int maxLengthSoFar = 0; // Length of the longest increasing subsequence that
// ends at some index j < i and has the element
// nums[j] < nums[i].
for (int j=0; j<i; j++) { // For all previous elements.
if (nums[j] < nums[i]) { // if the element is smaller.
maxLengthSoFar = max(maxLengthSoFar, dp[j]);
}
}
dp[i] = maxLengthSoFar+1;
}
return *max_element(dp.begin(), dp.end());
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.