Longest Increasing Subsequence

  • tags: [DP_Sequence]

Question

Problem Statement

Given an unsorted array of integers, find the length of longest increasing
subsequence.

For example,

Given [10, 9, 2, 5, 3, 7, 101, 18],

The longest increasing subsequence is [2, 3, 7, 101], therefore the length
is 4. Note that 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?

Credits:

Special thanks to @pbrother for
adding this problem and creating all test cases.

题解1 - 双重 for 循环

由题意知这种题应该是单序列动态规划题，结合四要素，可定义f[i]为前i个数字中的 LIC 数目，那么问题来了，接下来的状态转移方程如何写？似乎写不出来… 再仔细看看 LIS 的定义，状态转移的关键一环应该为数字本身而不是最后返回的结果(数目)，那么理所当然的，我们应定义f[i]为前i个数字中以第i个数字结尾的 LIS 长度，相应的状态转移方程为f[i] = {1 + max{f[j]} where j < i, nums[j] < nums[i]}, 该转移方程的含义为在所有满足以上条件的 j 中将最大的f[j] 赋予f[i], 如果上式不满足，则f[i] = 1. 具体实现时不能直接使用f[i] = 1 + max(f[j]), 应为若if f[i] < 1 + f[j], f[i] = 1 + f[j]. 最后返回 max(f[]). 需要注意的是 LIS 的含义，序列中是否可以包含相等的值。如果包含，则改为 nums[j] < nums[i].

Python

  1. class Solution(object):
  2.     def lengthOfLIS(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: int
  6.         """
  7.         if nums is None or len(nums) == 0:
  8.             return 0
  10.         lis = [1] * len(nums)
  11.         for i in range(1, len(nums)):
  12.             for j in range(i):
  13.                 if nums[j] < nums[i] and lis[i] < 1 + lis[j]:
  14.                     lis[i] = 1 + lis[j]
  15.         return max(lis)

C++

  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.         if (nums.empty()) return 0;
  10.         int len = nums.size();
  11.         vector<int> lis(len, 1);
  13.         for (int i = 1; i < len; ++i) {
  14.             for (int j = 0; j < i; ++j) {
  15.                 if (nums[j] < nums[i] && (lis[i] < lis[j] + 1)) {
  16.                     lis[i] = 1 + lis[j];
  17.                 }
  18.             }
  19.         }
  21.         return *max_element(lis.begin(), lis.end());
  22.     }
  23. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: The integer array
  4.      * @return: The length of LIS (longest increasing subsequence)
  5.      */
  6.     public int longestIncreasingSubsequence(int[] nums) {
  7.         if (nums == null || nums.length == 0) return 0;
  9.         int[] lis = new int[nums.length];
  10.         Arrays.fill(lis, 1);
  12.         for (int i = 1; i < nums.length; i++) {
  13.             for (int j = 0; j < i; j++) {
  14.                 if (nums[j] < nums[i] && (lis[i] < lis[j] + 1)) {
  15.                     lis[i] = lis[j] + 1;
  16.                 }
  17.             }
  18.         }
  20.         // get the max lis
  21.         int max_lis = 0;
  22.         for (int i = 0; i < lis.length; i++) {
  23.             if (lis[i] > max_lis) {
  24.                 max_lis = lis[i];
  25.             }
  26.         }
  28.         return max_lis;
  29.     }
  30. }

源码分析

  1. 初始化数组，初始值为1
  2. 根据状态转移方程递推求得lis[i]
  3. 遍历lis 数组求得最大值

复杂度分析

使用了与 nums 等长的空间，空间复杂度 O(n). 两重 for 循环时间复杂度为 O(n^2), 遍历求得最大值，时间复杂度为 O(n), 故总的时间复杂度为 O(n^2).

题解2 - 巧用 lower_bound

谢谢 @mckelvin 补充！在题解1中我们每次更新 LIS 的值时均遍历了之前的值，那么这里面是否存在重复判断从而可以优化时间复杂度的方法呢？由 LIS 的定义可知，最终构成 LIS 的数列一定是一个递增有序数列，求 LIS 即在构造 LIS 递增数列，最终输出该数列长度即可。这种场景使用 lower_bound 十分合适，即首先将数组第一个元素置于lis 第一个元素，随后如果元素比 lis 中的最后一个元素还要大，则将该元素加入至 lis 末尾，反之则将其放入指定的位置。这里有个小小的问题就是最终构成的 lis 并不一定是题目要求的 lis, 只是在长度上和题目要求的结果一致。Binary Search - lower/upper bound 中对 lower_bound 的实现做了详述。

C++

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         if (nums.empty()) return 0;
  6.         vector<int> lis;
  7.         for (int i = 0; i < nums.size(); ++i) {
  8.             vector<int>::iterator it = lower_bound(lis.begin(), lis.end(), nums[i]);
  9.             if (it == lis.end()) {
  10.                 lis.push_back(nums[i]);
  11.             } else {
  12.                 *it = nums[i];
  13.             }
  14.         }
  16.         return lis.size();
  17.     }
  18. };

源码分析

需要注意的是 lower_bound 的使用，需要找 nums[index] >= target, min(index).

复杂度分析

最坏空间复杂度为和 nums 等长，O(n). for 循环加上二分查找最坏情况下时间复杂度为 O(n \log n)

Follow up

上述问题均只输出最大值，现在需要输出 LIS 中的每一个原始元素值。

题解1 - LIS

由于以上递归推导式只能返回最大值，如果现在需要返回 LIS 中的每个元素，直观来讲，构成 LIS 数组中的值对应的原数组值即为我们想要的结果。我们不妨从后往前考虑，依次移除 lis[i] 数组中的值(减一)和索引，遇到和 lis[i]的值相等的 LIS 时即加入到最终返回结果。

Java

  1. import java.util.*;
  3. public class Solution {
  4.     /**
  5.      * @param nums: The integer array
  6.      * @return: LIS array
  7.      */
  8.     public int[] longestIncreasingSubsequence(int[] nums) {
  9.         if (nums == null || nums.length == 0) return null;
  11.         int[] lis = new int[nums.length];
  12.         Arrays.fill(lis, 1);
  14.         for (int i = 1; i < nums.length; i++) {
  15.             for (int j = 0; j < i; j++) {
  16.                 if (nums[j] <= nums[i] && (lis[i] < lis[j] + 1)) {
  17.                     lis[i] = lis[j] + 1;
  18.                 }
  19.             }
  20.         }
  22.         // get the max lis
  23.         int max_lis = 0, index = 0;
  24.         for (int i = 0; i < lis.length; i++) {
  25.             if (lis[i] > max_lis) {
  26.                 max_lis = lis[i];
  27.                 index = i;
  28.             }
  29.         }
  31.         // get result
  32.         int[] result = new int[max_lis];
  33.         for (int i = index; i >= 0; i--) {
  34.             if (lis[i] == max_lis) {
  35.                 result[max_lis - 1] = nums[i];
  36.                 max_lis--;
  37.             }
  38.         }
  40.         return result;
  41.     }
  43.     public static void main(String[] args) {
  44.         int[] nums = new int[]{5, 4, 1, 2, 3};
  45.         Solution sol = new Solution();
  46.         int[] result = sol.longestIncreasingSubsequence(nums);
  47.         for (int i : result) {
  48.             System.out.println(i);
  49.         }
  50.     }
  51. }

关于// get result 那一节中为何max_lis 自减一定是会得到最终想要的结果？假如有和其一样的lis如何破？根据 DP 中状态的定义可知正好为其逆过程，只不过答案不唯一，反向输出的答案输出的是最靠右的结果。