【必备算法】动态规划：LeetCode题（三）53. 最大子序和，300. 最长上升子序列

53. 最大子序和¹

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解法：动态规划

• 思路：分解模型且存在重复子问题（==>求每个求每个位置的最大子序和，然后找最值）。递推公式，problem(i) = max(problem(i - 1), 0) + nums[i]，
  • 状态数组：d[i]。到第i位时的最大子序和
  • 初始状态：d[0] = nums[0]。第一个元素的最大子序和就是自己。
  • 状态方程：d[i] = max(d[i - 1], 0) + nums[i]。当前的子序和 = 前一位子序和大于0 ？d[i-1]+当前值 : 当前值
  • 最终状态：状态数组中最大的那个
• 复杂度
  • Time：O（n）
  • Space：O（n）

public int maxSubArray(int[] nums) {
        int[] d = new int[nums.length];
        int max = Integer.MIN_VALUE;
    	// 初始状态
        d[0] = nums[0];
        // 状态递推
        for (int i = 1; i < nums.length; i++) 
            d[i] = Math.max(0, d[i - 1]) + nums[i];
    	// 找到最大的d[i]
        for (int i = 0; i < nums.length; i++) 
            max = Math.max(max, d[i]);
        return max;
}

这里可以对状态数组进行优化，优化成单个变量

//  Time：O（n） Space：O（1）
public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur = cur <= 0 ? nums[i] : (cur + nums[i]);
            max = Math.max(max, cur);
        }
        return max;
}

300. 最长上升子序列²

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

示例:

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

说明:

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

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

解法：动态规划

注意，这里区分三个概念：

• 子串："abc"的子串不包括“ac”
• 子序列：[1,2,3]的子序列包括[1,3]
• 连续子数组：[1,2,3]的连续子数组不包括[1,3]

• 思路：分解模型且存在重复子问题（==>求每个位置的最长上升序列长度，然后找最值）。递推公式，problem(i) = problem(前一个比它小的元素) + 1。
  • 状态数组：d[i]。到第 i 位时的上升序列长度
  • 初始状态：d[0] = nums[0] ,d[1] = max(nums[0], nums[1])。因为d[2]可能同时大于d[0]和d[1]，所以也要初始
  • 状态方程：d(i) = max(d(i),d(前一个小)+1)。本来是d(i) = d(前一个比他小的元素) + 1 ，但可能存在多个比当前元素小的
  • 最终状态：状态数组中最大的那个

public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] memo = new int[nums.length];
        // 初始状态
        for (int i = 0; i < nums.length; i++)
            memo[i] = 1;
        // 状态递推
        for (int i = 1; i < nums.length; i++) 
        	// 因为可能有多个小于当前元素的，所以要遍历[0,i]去找他们中d[i]最大的
            for (int j = 0; j < i; j++) 
                if (nums[j] < nums[i]) 
                    memo[i] = Math.max(memo[j] + 1, memo[i]);
        // 寻找最大的d[i]
        int res = 1;
        for (int i = 0; i < nums.length; i++) 
            res = Math.max(res, memo[i]);
        return res;
}

本题不能优化状态数组成单个变量，因为当前状态的递推需要前面所有的状态