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

忘是亡心i 2022-12-20 01:54 33阅读 0赞

## [53. 最大子序和¹][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. 最长上升子序列²][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;
    }

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

##  ##

[53.]: https://leetcode-cn.com/problems/maximum-subarray/
[300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/