数组--53.最大子数组和/medium

2024-01-01 08:33:21

1、题目

给你一个整数数组 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 <= 105
-104 <= nums[i] <= 104

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

2、题目分析

求连续子数组的最大和,意味着对数组切分成多段,此时有 2 个要点:

  1. 如何切分,什么情况下子数组还能接着往后连续下去?
    求连续子数组的最大和,当子数组遇到新值时,
    如果加该值,子数组的和大于该值,则让子数组继续往下遍历的效果更佳,
    如果加该值,子数组的和小于该值,则不如让子数组在这做分割,然后下一个子数组从该新值开始。
  2. 对切分后的每一段数据做什么操作?
    进行值的累加,并对比记录下各段子数组和的最大值。

3、解题步骤

  1. 初始化 2 个值:
    a. 每段子数组的和=0
    b. 各段子数组和的最大值max=数组首个元素(不能初始化为0,避免数组各段子数组和的最大值小于0的情况)
  2. 遍历数组,并做 2 步:
    a. sum = max(上个子数组 + 当前新值,当前新值)。即判断上个子数组是否还往下扩展,还是在此截止。
    b. max = max(sum, max)。即max对比记录下各段子数组和的最大值。

4、复杂度最优解代码示例

    public int maxSubArray(int[] nums) {
        int sum = 0;
        // 踩坑,这里不能初始化为 0。如当数组只有1个元素,且为负数时,max不会被替换为负数。
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
        	// a. sum = max(上个子数组 + 当前新值,当前新值)。即判断上个子数组是否还往下扩展,还是在此截止。
            sum = Math.max(sum + nums[i], nums[i]);
            // b. max = max(sum, max)。即max对比记录下各段子数组和的最大值。
            max = Math.max(sum, max);
        }
        return max;
    }

5、抽象与扩展

求连续子数组/子串的和值等问题,核心就是找到子数组/子串是否往下扩展的条件。

如本题中,
子数组要往下扩展的条件就是,子数组的和 + 新值 > 新值,则子数组接着往下扩展。
否则,新值 另起一个子数组。

文章来源:https://blog.csdn.net/fujuacm/article/details/135316573
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。