【Leetcode hot 100】53.最大子数组和

问题链接

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 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

问题解答

要解决最大子数组和的问题，我们可以使用动态规划的方法，通过一次遍历数组来高效地计算出结果。

方法思路

动态规划的核心思想是利用已知的子问题结果来推导更大问题的结果。对于本题，我们可以定义两个变量：

• currentSum：表示以当前元素结尾的最大子数组和。
• maxSum：表示遍历到当前位置时，所有可能的子数组和中的最大值。

状态转移方程：对于数组中的每个元素 nums[i]，有两种选择：

1. 将当前元素加入到前面的子数组中（即 currentSum + nums[i]）。
2. 从当前元素开始重新创建一个子数组（即 nums[i]）。

我们取这两种选择中的较大值作为 currentSum 的新值，即 currentSum = max(nums[i], currentSum + nums[i])。同时，每次更新 currentSum 后，都需要更新 maxSum 以确保其始终是当前的最大值。

解决代码

class Solution {public int maxSubArray(int[] nums) {// 初始化当前子数组和以及最大子数组和为第一个元素int currentSum = nums[0];int maxSum = nums[0];// 从第二个元素开始遍历for (int i = 1; i < nums.length; i++) {// 决定当前元素是加入前面的子数组，还是重新开始currentSum = Math.max(nums[i], currentSum + nums[i]);// 更新最大子数组和maxSum = Math.max(maxSum, currentSum);}return maxSum;}
}

代码解释

1. 初始化：将 currentSum 和 maxSum 都初始化为数组的第一个元素，因为至少包含一个元素的子数组最大和至少是第一个元素本身。
2. 遍历数组：从第二个元素开始遍历，对于每个元素：
   • 计算 currentSum：判断是将当前元素加入前面的子数组，还是重新开始一个子数组。
   • 更新 maxSum：确保 maxSum 始终是遍历到当前位置时的最大子数组和。
3. 返回结果：遍历结束后，maxSum 即为整个数组的最大子数组和。

这种方法的时间复杂度是 O(n)（仅需遍历一次数组），空间复杂度是 O(1)（仅使用了两个额外变量），效率非常高。