2021/3/25 最长递增子序列

题目描述

描述转载自力扣《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

解题思路

1. 先讲结论：这种类型的题目是考虑 f(i) 前 f(0) 到 f(i - 1) 的最优解的单串问题。
   
2. 我们用动态规划解决这个问题，就要对问题进行拆分。通常，对于这种单串数组，我们有两种解决办法，第一个是对半拆分数组，第二个是每次减少 1 个元素，有 [0..i-1] 组成子问题。
   
3. 假设我们对半拆分问题，借用示例 1 的数组，拆分后得到 [10,9,2,5] 和 [3,7,101,18]，两个子问题的最优解是 [2, 5] 和 [3, 7, 18]，我们会发现，这两个子问题很难组合起来，所以我们考虑另一种拆分方案。
   
4. 我们每次减少末尾的元素，假设末尾元素角标是 i，那么我们就可以设 f(i) 是以元素 i 结尾的最优解。也就是说，我们需要从 [0..i-1] 中，找到最长递增子序列的长度，然后长度 + 1，就得到了 f(i)。
5. 根据(4)，我们得出状态转移方程 ，其中 是 前面的所有子问题

Java代码实现

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);    // 假设所有的数都找不到递增子序列，也就是说这个数组是个递减数组，则所有元素结尾的递增子序列长度都为 1，只有该元素本身。
        int max = 1;    // 记录 f(i) 中最长的长度
        for (int i = 1; i < nums.length; ++i) {    // 计算 f(i)
            for (int j = 0; j < i; ++j) {    // 遍历 f(0) 到 f(i-1)，选择最优解
                if (nums[j] < nums[i]) {
                    // 转移方程：f(n) = max(f(i)) + 1
                    dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
                    max = max > dp[i] ? max : dp[i];
                }
            }
        }
        return max;
    }

}