53. 最大子数组和

2022-2-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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

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

解题方法一

/**
     * 暴力双循环
     * 力扣提交直接超出时间限制
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int maxValue = nums[0];
        if (nums.length == 1) return maxValue;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                maxValue = Math.max(maxValue, sum);
            }
        }
        return maxValue;
    }

解题方法二

/**
     * 动态规划
     *
     * 1.首先明确dp数组的含义，dp[i]表示以nums[i]点结尾的连续子数组的最大和。
     *
     * 2.然后推导状态方程，以nums[i]为结尾的连续子数组有两种情况。
     * 情况1. nums[i]前面没有数，自己组成长度为1的子数组。
     * 此时以nums[i]点结尾的连续子数组的最大和就是nums[i].即 dp[i] = nums[i].
     *
     * 情况2. nums[i]前面有数，与前面的数组成子数组，
     * 此时以nums[i]点结尾的连续子数组的最大和就是nums[i]加上以nums[i-1]为结尾的连续子数组的最大和。
     * 即 dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]).
     *
     * 时间复杂度：O(N) ，这里 N 是输入数组的长度。
     *
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums){
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxValue = dp[0];
        for (int i = 1; i < nums.length; i++) {
            // dp[i]表示nums中以nums[i]结尾的最大子序和
            // 表示当前元素是否要与前边元素相加
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxValue = Math.max(maxValue,dp[i]);
        }

        return maxValue;
    }

解题方法三

/**
     * 分治思想
     *
     * 将原数组划分为左右两个数组后，原数组中拥有最大和的连续子数组的位置有三张情况。
     * 情况1. 原数组中拥有最大和的连续子数组的元素都在左边的子数组中。
     * 情况2. 原数组中拥有最大和的连续子数组的元素都在右边的子数组中。
     * 情况3. 原数组中拥有最大和的连续子数组的元素跨越了左右数组。
     * 分别求出，3中情况的最大和，取最大，就是原数组的连续子数组的最大和。
     *
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums){
        return getMax(nums, 0, nums.length - 1);
    }

    private int getMax(int[] nums, int L, int R) {
        if (L == R) return nums[L];
        int mid = L + ((R - L) >> 1);
        int leftSum = getMax(nums, L, mid);
        int rightSum = getMax(nums, mid + 1, R);
        int crossSum = getCrossMax(nums, L, R);
        return Math.max(crossSum, Math.max(leftSum, rightSum));
    }

    private int getCrossMax(int[] nums, int L, int R) {
        int mid = L + ((R - L) >> 1);
        int leftSum = nums[mid];
        int leftMax = leftSum;
        for (int i = mid - 1;i >= L;i--){
            leftSum += nums[i];
            leftMax = Math.max(leftMax,leftSum);
        }
        int rightSum = nums[mid + 1];
        int rightMax = rightSum;
        for (int i = mid + 2;i <= R;i++){
            rightSum += nums[i];
            rightMax = Math.max(rightMax,rightSum);
        }
        return leftMax + rightMax;
    }