最长递增子序列问题(Longest Increasing Subsquence, LIS)

• • 问题
  • 思路
  • 代码实现（C++）
  • 总结

LeetCode.300

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2
输入：nums = [0,1,0,3,2,3]
输出：4

示例3
输入：nums = [7,7,7,7,7,7,7]
输出：1

首先要明确题中所求严格递增子序列是可以不连续的，但元素在原数列中的先后顺序在子序列中要保持。
对于以某个元素结尾的数列，其严格最长递增子序列就是它前面小于它的元素的严格最长递增子序列加上自己，前面比它大的元素直接排除，因为不可能构成依然递增的序列。

所以如果能求出前面元素的LIS长度, 答案显而易见，这也就是动态规划的核心思路，类似于数学归纳法。

总结动态规划求解思路如下：

• 首先确定DP数组含义：dp[i]表示以nums[i]结尾的最长严格递增子序列长度为多少
• 然后写状态转移方程：dp[i] = max(dp[i], dp[j] + 1)，这里nums[j] < nums[i]
• 确定base case：初始化 dp[i] = 1
• 举例DP table：
  以nums = [10,9,2,5,3,7,101,18]为例

最终的最大长度即DP table的元素最大值

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        vector dp(nums.size(), 1);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        int res = 0;
        for (int i = 0; i < dp.size(); i++) res = max(res, dp[i]);
        return res;
    }
};

本题DP解法的时间复杂度为 O ( n 2 ) O(n^2) O(n2) ；
DP算法的重点：
1）确定DP table含义
2）已知0, …, i - 1的DP值，如何利用这些值求出dp[i]，也就是状态转移方程的建立。
解决了这两点，问题迎刃而解。