[LintCode]最長上昇サブシーケンス
3015 ワード
動的計画:
lis[i] = max_{j = 0, 1, ..., i - 1, nums[j] < nums[i]} lis[j] + 1
lis[i] = max_{j = 0, 1, ..., i - 1, nums[j] < nums[i]} lis[j] + 1
1 class Solution {
2 public:
3 /**
4 * @param nums: The integer array
5 * @return: The length of LIS (longest increasing subsequence)
6 */
7 int longestIncreasingSubsequence(vector<int> nums) {
8 // write your code here
9 vector<int> lis(nums.size(), 1);
10 int maxlen = 0;
11 for (int i = 1; i < (int)nums.size(); i++) {
12 for (int j = 0; j < i; j++)
13 if (nums[j] <= nums[i] && lis[j] + 1 > lis[i])
14 lis[i] = lis[j] + 1;
15 maxlen = max(maxlen, lis[i]);
16 }
17 return maxlen;
18 }
19 };