300 - Longest Increasing Subsequence

解法一 - 暴力法

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
return findLIS(nums, 0, -1);
}

private:
int findLIS(vector<int>& nums, int curIdx, int prevIdx) {
if(curIdx == nums.size())
return 0;

int c1 = 0;
// include the nums[curIdx] when it is larger than the previous included value
if(prevIdx == -1 || nums[curIdx] > nums[prevIdx]) {
c1 = 1 + findLIS(nums, curIdx+1, curIdx);
}

int c2 = findLIS(nums, curIdx+1, prevIdx);

return max(c1, c2);
}
};
``````

解法二 - Memoization

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<vector<int>> memo(nums.size()+1, vector<int>(nums.size()+1, -1));
return findLIS(memo, nums, 0, -1);
}

private:
int findLIS(vector<vector<int>>& memo, vector<int>& nums, int curIdx, int prevIdx) {
if(curIdx == nums.size())
return 0;

if(memo[curIdx+1][prevIdx+1] == -1) {
int c1 = 0;
// include the nums[curIdx] when it is larger than the previous included value
if(prevIdx == -1 || nums[curIdx] > nums[prevIdx]) {
c1 = 1 + findLIS(memo, nums, curIdx+1, curIdx);
}
int c2 = findLIS(memo, nums, curIdx+1, prevIdx);

memo[curIdx+1][prevIdx+1] = max(c1, c2);
}

return memo[curIdx+1][prevIdx+1];
}
};
``````

Runtime: 500 ms, faster than 5.76% of C++ online submissions for Longest Increasing Subsequence. Memory Usage: 111.5 MB, less than 6.25% of C++ online submissions for Longest Increasing Subsequence.

解法三 - DP

dp[i] = dp[j]+1 if (dp[j]+1 > dp[i] && nums[i] > nums[j]) for all j < i

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;

vector<int> dp(nums.size());
dp[0] = 1;

int maxLen = 1;
for(int i=1; i<nums.size(); i++) {
dp[i] = 1;
for(int j=0; j<i; j++) {
if(nums[j] < nums[i] && dp[j]+1 > dp[i]) {
dp[i] = dp[j]+1;
maxLen = max(maxLen, dp[i]);
}
}
}

return maxLen;
}
};
``````