最长上升子序列 - Longest Increasing Subsequence

Posted on Edited on In , Views: Word count in article: 35 Reading time ≈ 1 mins.

经典 dp，记录模板。

最长上升子序列

1
2
3
4
5
6
7
8
9
int LIS(vector<int>& nums) {
  int ans = 0;
  vector<int> dp(nums.size(), 1);
  for (int i = 0; i < (int)nums.size(); i++)
    for (int j = 0; j < i; j++)
      if (nums[i] > nums[j])
        dp[i] = max(dp[i], dp[j] + 1), ans = max(ans, dp[i]); // dp[i] 表示以 i 结尾的 LIS 长度
  return ans;
}

优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int lengthOfLIS(vector<int>& nums) {
    int len = 1, n = nums.size();
    if (len == 0) return 0;
    vector<int> d(nums.size() + 1);
    d[len] = nums[0];
    for (int i = 0; i < n; i++) {
      if (nums[i] > d[len]) {
        d[++len] = nums[i];
      } else {
        int l = 1, r = len, m;
        int pos = 0;
        while (l <= r) {
          m = (l + r) / 2;
          if (d[m] < nums[i]) {
            pos = m;
            l = m + 1;
          } else {
            r = m - 1;
          }
        }
        d[pos + 1] = nums[i];
      }
    }
    return len;
  }