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\le nums.length\le {10}^5$
• $-{10}^4\le nums[i]\le {10}^4$

进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解法一(贪心)

思路分析

1. 即对于最大值, 应该是尽量大于0;
2. 则两个数相加, 尽量保证前一个数是大于0的, 这样与第二个数的和才是有机会是最大的;
3. 所以对于子数组进行求和时, 若前一段子数组和小于0, 则舍弃, 以当前元素为新的子数组起始节点;
4. 若前一段子数组和大于0, 则尝试与当前元素相加, 再判断是否为子数组和的最大值;

实现代码

class Solution {
    public int maxSubArray(int[] nums) {
		int result = Integer.MIN_VALUE;
		int count = 0;
        for (int num : nums) {
            count += num;
            if (count > result) // 时刻更新最大和
				result = count;
            if (count < 0)
				count = 0;	// 当连续子数组和小于0时 重置连续和为0
        }
		return result;
    }
}

运行结果

解答成功:

执行耗时:1 ms,击败了100.00% 的Java用户

内存消耗:55.6 MB,击败了93.47% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

解法二(动态规划)

思路分析:

1. 首先确定dp数组含义, 则dp[i]表示以i为最后元素的子数组,最大和为dp[i];
2. 推到dp公式, 对于两个数求和, 只有当一个数与一个不小于0的数相加时才会变大, 因此对于当前状态,dp[i], 只有当dp[i-1] > 0时, nums[i] + dp[i-1]会变大, 即最大和变大, 否则则保留dp[i] = nums[i];
3. 对于dp数组如何初始化, 则可以直接使用原数组进行计算, 即nums[i] = nums[i] + nums[i-1] > 0 ? nums[i-1]:0;
4. 对于dp数组的遍历顺序, 则从左往右依次累加即可;

实现代码

class Solution {
	public int maxSubArray(int[] nums) {
		// 直接使用nums作为dp数组
		// 公式为：nums[i] = nums[i] + nums[i-1]>0?nums[i-1]:0;
		int ans = nums[0];
		for (int i = 1; i < nums.length; ++ i) {
			if (nums[i-1] > 0) {
				nums[i] += nums[i-1];   // 和大于0的数相加 才会变大
			}
			ans = Math.max(ans, nums[i]);   // 不断更新 保证是最大值
		}
		return ans;
	}
}

运行结果

2024/10/06 17:11:25

解答成功:

执行耗时:1 ms,击败了100.00% 的Java用户

内存消耗:55.9 MB,击败了64.74% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$