剑指 Offer 42. 连续子数组的最大和

我不是女神ヾ 2022-11-21 11:33 149阅读 0赞

# 题目 #

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

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

示例1:

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

提示：

*  1 <= arr.length <= 10^5
 *  \-100 <= arr\[i\] <= 100

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof][https_leetcode-cn.com_problems_lian-xu-zi-shu-zu-de-zui-da-he-lcof]

# 解题思路 #

使用动态规划

当前元素下标为i，则连续子数组最大和为以下两者中的最大值：

*  前i - 1个元素最大连续子数组之和为0或正数时，前i - 1个元素的最大连续子数组之和 + 当前下标元素值
 *  前i - 1个元素最大连续子数组之和为0或负数时，当前下标元素值

# 代码 #

class Solution { 
        public int maxSubArray(int[] nums) { 
            // 初始化最大值和当前最大值
            int max = nums[0];
            int curMax = nums[0];
            for (int i = 1; i < nums.length; i++) { 
                // 当前最大值为，当前值和当前值加上之前的最大值两者中更大的一个
                // 下标为i的元素，不管哪种情况都包括在了其中，所以子数组一定是连续的
                curMax = Math.max(nums[i], nums[i] + curMax);
                // 获取最大值
                max = Math.max(max, curMax);
            }
            return max;
        }
    }

# 复杂度 #

*  时间复杂度:O(n),n为数组的长度
 *  空间复杂度:O(1),常数级额外空间占用

[https_leetcode-cn.com_problems_lian-xu-zi-shu-zu-de-zui-da-he-lcof]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof