Longest Increasing Subsequence
思路:DP
- 状态表示:f[i]是以nums[i]结尾的子序列长度的最大值
- 时间复杂度:O(n^2)
- 参考:yxc
题目
/*
* @lc app=leetcode id=300 lang=cpp
*
* [300] Longest Increasing Subsequence
*
* https://leetcode.com/problems/longest-increasing-subsequence/description/
*
* algorithms
* Medium (41.22%)
* Likes: 2907
* Dislikes: 68
* Total Accepted: 254.7K
* Total Submissions: 616.2K
* Testcase Example: '[10,9,2,5,3,7,101,18]'
*
* Given an unsorted array of integers, find the length of longest increasing
* subsequence.
*
* Example:
*
*
* Input: [10,9,2,5,3,7,101,18]
* Output: 4
* Explanation: The longest increasing subsequence is [2,3,7,101], therefore
* the length is 4.
*
* Note:
*
*
* There may be more than one LIS combination, it is only necessary for you to
* return the length.
* Your algorithm should run in O(n^2) complexity.
*
*
* Follow up: Could you improve it to O(n log n) time complexity?
*
*/
代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//切入点:习惯考虑以nums[i]结尾的子序列
//状态表示:f[i] 以nums[i]结尾的子序列长度的最大值
//状态计算:划分集合:考虑倒是第二个数nums[j],因为倒数第二个数可以取nums[0]~nums[j]
//共i种情况(当只有i时另考虑)所以 f[i] = f[j] + 1;
int n = nums.size();
vector<int> f(n);
// 先初始化f[i], 序列只有nums[i]时, f[i] = 1
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (nums[j] < nums[i])
f[i] = max(f[i], f[j] + 1);
}
// 这样就求出了以每个点结尾的序列的长度的最大值,然后遍历数组,求max
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, f[i]);
return res;
}
};