题目
给定一个无序整型数组, 找出最大的递增子序列的长度.
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4 // [2,3,7,101]
思路1
递归.
int lengthOfLISHelper(vector<int>& nums, int flag, int pos) {
if (pos >= nums.size()) return 0;
int count = 0;
if (nums[pos] > flag) {
count = lengthOfLISHelper(nums, nums[pos], pos+1) + 1;
}
int nextCount = lengthOfLISHelper(nums, flag, pos+1);
return max(nextCount, count);
}
int lengthOfLIS(vector<int>& nums) {
return lengthOfLISHelper(nums, INT_MIN, 0);
}
思路2
DP.
int lengthOfLIS2(vector<int>& nums) {
if (nums.empty()) return 0;
// 记录nums[i]的最大子序列个数
vector<int> dp(nums.size());
int count = 1;
dp[0] = 1;
for (int i = 1; i < nums.size(); i++) {
int maxCount = 0;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
maxCount = max(maxCount, dp[j]);
}
}
dp[i] = maxCount + 1;
count = max(count, dp[i]);
}
return count;
}
总结
求最值, 优先考虑使用DP. 熟练掌握递归思想, 递归难以理解, 但是可以熟能生巧.
