LeetCode.53.最大子序和（简单）

题目

LeetCode.53.最大子序和（简单）

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

题解

思路

最值问题考虑用动态规划，从某个状态倒推，拆解为上一个状态+所有可能的最小步骤，看是否符合动态规划的条件。

划分子问题

设dp[i]为以nums[i]为结尾的连续子数组的最大和。

求dp[i]肯定是要加上nums[i]的，此时合成子数组有两种选择：

1. nums[i]单独为一个子数组
2. nums[i]和前面的连续子数组合并

如何选择？

1. 如果 dp[i - 1] + nums[i] > nums[i]，那么dp[i] = dp[i - 1] + nums[i]。
2. 如果 dp[i - 1] + nums[i] < nums[i]，那nums[i]单独成子数组后和反而更大，dp[i] = nums[i]。

状态转移方程

dp[i] = max(dp[i - 1] + nums[i], nums[i])

边界处理

dp[0]就是nums[0]本身了，只包含自己的子数组。

空间优化

dp[i]只依赖于前一项的递推，可以不用数组，只用一个变量记录上一个值。

代码

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        var pre = 0
        var maxSum = nums[0]
        for (num in nums) {
            val cur = maxOf(pre + num, num)
            maxSum = maxOf(maxSum, cur)
            pre = cur
        }
        return maxSum
    }
}