题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

题解

这道题我真的想了很久，各种胡思乱想，最终沾了点边，想到了数组dp[i]中存储的应该是以num[i]结尾的子序列的最大长度，但实现起来复杂度非常高。实现代码如下：

 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
26
27
28
29

int interLenghtOfLIS(vector<int>& nums, int pos, vector<vector<int>> &vv) {
  int max_len = 1;
  
  for (int i = pos - 1; i >= 0; i--) {
      if (nums[i] < nums[pos]) {
          if (vv[pos][i] != 0) {
              max_len = max(max_len, vv[pos][i]);
          }
          else {
              max_len = max(max_len, interLenghtOfLIS(nums, i, vv) + 1);
          }
          
          vv[pos][i] = max_len;
      }
  }

  return max_len;
}

int lengthOfLIS(vector<int>& nums) {
  vector<vector<int>> vv(nums.size());
  for (auto &v : vv) v.resize(nums.size());
  int max_len = 0;
  for (int i = nums.size() - 1; i >= 0; i--) {
      max_len = max(max_len, interLenghtOfLIS(nums, i, vv));
  }
  
  return max_len;
}

以数组 [10,9,2,5,3,7,101,18]为例说下上面代码的思想，我们从后往前走，首先最后一个数为18，我们以18为结尾，找所有比18小的数，并获取以他们自身结尾的最大子序列长度，再加上18，即得到以18结尾的最大子序列的长度。比如说，我们往前找到7，那么我们得到以7结尾的最大子序列的长度，那么再加上1，就得到了7，18结尾的最大子序列的长度。如果我们找所有比18小的数的子序列的最大长度，然后再加上18这一个，不就得到了以18结尾的最大子序列的长度？

之后依次往前，再去找以101结尾的最大子序列的长度，再找以7结尾的最大子序列的长度。最终得到以所有数结尾的最大子序列的长度，并得到最大的一个值。这个最大的值就是我们想要的结果。

但上面的程序实现太复杂了，在运行过程中超时。

最终无奈看了题解，看完之后，发现自己的思路实际上已经很接近了。题解的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> v;
    v.resize(nums.size());
    int max_len = 1;
    for (int i = 0; i < nums.size(); i++) {
        v[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                v[i] = max(v[i], v[j] + 1);
                max_len = max(max_len, v[i]);
            }
        }
    }

    return max_len;
}

在动态规划实现中，是从前往后算，还以 [10,9,2,5,3,7,101,18]为例，dp[i]数组的结果中存得依旧是以nums[i]结尾的最大子序列的长度。那么dp[i]就为在它前面所有比nums[i]小的数据子序列长度中的最大值+1。比如说我们求5结尾的子序列的长度，在5前面比他小的只有2，我们只要拿以2结尾的最大子序列的长度+1就得到了以5结尾的最大子序列的长度。其他情况同理。

实际上感觉自己的递归稍微改一下就成了这种方式了，果然还是自己太垃圾。

之前还有一道题是最大子序和，与它对比来看，会发现这类最大子序类的题目中，dp[i]数组的含义都是以nums[i]结尾的数组的结果，这点经验需要记下来。