題目
給定一個(gè)無序整型數(shù)組, 找出最大的遞增子序列的長(zhǎng)度.
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]的最大子序列個(gè)數(shù)
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;
}
總結(jié)
求最值, 優(yōu)先考慮使用DP. 熟練掌握遞歸思想, 遞歸難以理解, 但是可以熟能生巧.
