力扣热题100题-最大子数组和

算法力扣热题100题待回顾

发布日期: 2022-06-18

更新日期: 2024-10-08

文章字数: 1k

阅读时长: 4 分

阅读次数:

给你一个整数数组 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) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/maximum-subarray

暴力解法：

/**
    暴力解法：
     */
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length ;i++){
            max = Math.max(max,nums[i]);
            int temp = nums[i];
            for(int j = i+1 ; j < nums.length ;j++){
                temp = temp + nums[j];
                max = Math.max(max,temp);
            }
        }
        return max;
    }

力扣显示超时，思考如何优化算法的时间复杂度。

动态规划版本一：

public int maxSubArray2(int[] nums) {
    int len = nums.length;
    // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
    int[] dp = new int[len];
    dp[0] = nums[0];

    for (int i = 1; i < len; i++) {
        //当前数加上一个大于0的数，肯定是大于当前数，否则就等于当前数
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i];
        } else {
            dp[i] = nums[i];
        }
    }

    // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
    int res = dp[0];
    for (int i = 1; i < len; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

动态规划版本二：

/**
     * 动态规划
     */
    public int maxSubArray(int[] nums) {
        //f(n) = max(f(n-1) + nums[n], nums[n]);
        // 前置的和
        int preSum = 0;

        // 最大值，所有的前置和的最大值。
        int max = nums[0];

        for (int num : nums) {
            preSum = Math.max(preSum + num, num);
            max = Math.max(max, preSum);
        }
        return max;
    }

动态规划的方程必须要理解一个点：

子问题的描述还有不确定的地方这件事情叫做「有后效性」; 为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。

方法二：分治法

连续子序列的最大和主要由这三部分子区间里元素的最大和得到：

第 1 部分：子区间 [left, mid]；
第 2 部分：子区间 [mid + 1, right]；
第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。

对这三个部分求最大值即可。

public int maxSubArray(int[] nums) {
        int len = nums.length;
        return maxSubArraySum(nums, 0, len-1);
    }

//- 第 1 部分：子区间 [left, mid]；
//- 第 2 部分：子区间 [mid + 1, right]；
//- 第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。
    //最大子数组和
    private int maxSubArraySum(int[] nums, int left, int right) {

        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        //
        return Math.max(maxSubArraySum(nums, left, mid),
                Math.max(maxSubArraySum(nums, left + 1, right),
                        maxCrossingSum(nums, left, mid, right)));
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }