目录

连续子数组的最大和

描述

示例1

解释

提示

方法：动态规划

连续子数组的最大和

描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1

输入

nums = [-2,1,-3,4,-1,2,1,-5,4]

输出

6

解释

连续子数组 [4,-1,2,1] 的和最大，为 6。

提示

方法：动态规划

我们可以定义dp[i]为以元素arr[i]结尾时的最大子数组和，那么就可以得递推式：

• 若dp[i-1]<0：则前面得子数组和为负数，dp[i]=arr[i]
• 若dp[i-1]>=0：则前面得子数组和为非负数，dp[i]=dp[i-1]+arr[i]

最后遍历dp数组，找到最大值就是本题的解。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length==1) return nums[0];
        int[] dp=new int[nums.length];//dp[i]代表以元素i结尾时的子数组最大和
        dp[0]=nums[0];//初始化
        for (int i = 1; i < nums.length; i++) {
            if (dp[i-1]<0){
                dp[i]=nums[i];//如果前面的子数组最大和为负数，则舍去前面的部分，从当前元素开始
            }else{
                dp[i]=dp[i-1]+nums[i];//如果前面的子数组和为正数，则加上当前元素
            }
        }
        int max=dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (max