【算法分析与设计】最大子数组和

题目

给你一个整数数组?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

方案一（暴力破解）

思路

三层for循环，

? ? ? ? 第一层：字段最左边坐标

? ? ? ? 第二层：子段最右边坐标

? ? ? ? 第三层：字段从左到右遍历

代码实现.

(这是书上的代码，默认是所有都是负数的情况下，最大值为0)；

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length;j++){
                int thisSum=0;
                for(int k=i;k<=j;k++){
                    thisSum=thisSum+nums[k];
                    if(thisSum>sum){
                        sum=thisSum;
                    }
                }
            }
        }
        return sum;
    }
}

方案二（分治递归）

思路

分治法不是这道题时间复杂度最优的解法，但可能是这道题最有挑战性的解法。分治法的算法设计、时间复杂度分析都并不容易。这个解法建议详细阅读，赶时间的同学可以先跳到下一个解法。

既然是分治法，我们首先要考虑的就是如何「分」。要计算数组?nums?的最大子数组和，我们从数组中间将数组一分为二，则子数组可能位于：

• 左半部分数组

• 右半部分数组

• 中间（穿过中间线）

将数组一分为二后，子数组可能位于的三个位置

其中，位于左半部分数组和位于右半部分数组的子数组，可以通过递归调用继续求解，这便是分治法的「治」。

对于穿过中间线的子数组，我们可以分别计算「中间线左侧的最大子数组和」以及「中间线右侧的最大子数组和」，把它们相加就得到「穿过中间线的最大子数组和」。

穿过中间线的子数组分左右两半计算

代码实现

public int maxSubArray(int[] nums) {
    return maxSubArray(nums, 0, nums.length - 1);
}
 
// 计算 nums[lo..hi] 的最大子数组和
// lo 表示 low，hi 表示 high
private int maxSubArray(int[] nums, int lo, int hi) {
    if (hi < lo) {
        return Integer.MIN_VALUE;
    } else if (hi == lo) {
        return nums[lo];
    }
    
    int mid = lo + (hi - lo) / 2;
    // 计算左半部分数组的最大子数组和
    int max_left = maxSubArray(nums, lo, mid);
    // 计算右半部分数组的最大子数组和
    int max_right = maxSubArray(nums, mid+1, hi);
    // 计算穿过中间线的子数组的最大和
    int max_mid = maxMidSubArray(nums, lo, mid, hi);
    return Math.max(max_left, Math.max(max_mid, max_right));
}
 
private int maxMidSubArray(int[] nums, int lo, int mid, int hi) {
    // 计算中间线左侧（且紧挨着中间线）的最大子数组和
    int max_mid_left = 0;
    if (mid >= lo) {
        max_mid_left = nums[mid];
        int sum = 0;
        for (int i = mid; i >= lo; i--) {
            sum += nums[i];
            max_mid_left = Math.max(max_mid_left, sum);
        }
    }
    
    // 计算中间线右侧（且紧挨着中间线）的最大子数组和
    int max_mid_right = 0;
    if (mid + 1 <= hi) {
        max_mid_right = nums[mid+1];
        int sum = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += nums[i];
            max_mid_right = Math.max(max_mid_right, sum);
        }
    }
    
    return max_mid_left + max_mid_right;
}

方案三（动态规划）

算法分析

1. 初始化两个变量 max 和 temp 为数组第一个元素 nums[0]。其中，max 用于记录全局最大子数组和，而 temp 用于记录当前子数组的和。

2. 使用一个循环遍历数组 nums，从第一个元素开始。

3. 在循环中，对于当前元素 nums[i]，更新 temp 的值，使其成为当前元素 nums[i] 和之前子数组的和中的较大者。这是通过 temp = Math.max(temp + nums[i], nums[i]) 实现的。这一步表示考虑是否将当前元素加入当前的子数组，或者重新开始一个新的子数组。

4. 在每一步中，都更新 max 的值，将其设为 temp 和 max 中的较大者。这样，max 始终记录着全局最大子数组和。

5. 循环结束后，max 中存储的就是整个数组中的最大子数组和

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int max=nums[0];
        int temp=0;
        int flag=0;
    
        for(int i=0;i<nums.length;i++){
            
            temp=Math.max(temp+nums[i],nums[i]);
            max=Math.max(temp,max);

        }
        return max;

    }

}