Leetcode 53.最大子数组和

题目要求

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

  • 子数组是数组中的一个连续部分。

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

示例2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

动态规划

动规五部曲

  1. 确定dp数组（dp table）以及下标的含义
    dp[i]表示以nums[i]结尾的最大子数组和

  2. 确定递推公式

    • 如果dp[i-1]>0,那么dp[i]=dp[i-1]+nums[i]
    • 如果dp[i-1]<=0,那么dp[i]=nums[i]
    • 综合起来：dp[i]=Math.max(dp[i-1]+nums[i],nums[i])
    • 最后的结果是取dp数组中的最大值

  3. dp数组如何初始化
    dp[0]=nums[0]

  4. 确定遍历顺序
    从前往后遍历

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}