LeetCode 0053. 最大子序和[动态规划详解]

原创

Yano_nankai

修改于 2021-03-04 17:42:59

2710

修改于 2021-03-04 17:42:59

文章被收录于专栏：二进制文集

题目描述

题目链接

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

```

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

定义 dpi 为 nums 中以 i 为结尾的连续子数组的最大和，则 dpi 要么是只使用了 numsi，要么是使用了 dpi-1 + numsi

则状态转移方程为：

dpi = Math.max(numsi + dpi - 1, numsi);

其实上述是可以优化的，只要 dpi-1 是>0 的，那么对结果就有贡献，dp 数组可以节省为 1 个变量，空间复杂度可以从 O(n) 减少到 O(1)。不过动态规划能把状态转移方程写出来就好了，其余的都是细节问题。

代码

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null) return 0;
        // 数组可省略
        int[] result = new int[nums.length];
        int max = nums[0];
        result[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            // f(i + 1) = max(f(i) + n[i + 1], n[i + 1])
            result[i] = Math.max(nums[i] + result[i - 1], nums[i]);
            max = Math.max(max, result[i]);
        }
        return max;
    }
}