0053. Maximum Subarray (E)

佚名 4年前 (2020-07-03) 算法 716人围观抢沙发百度已收录

Maximum Subarray (E)

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题意

找到给定数组中的一个子数组，使其和最大。

思路

与连续区间有关的问题很容易想到使用动态规划：dp[i]代表以nums[i]为结尾的各个子数组中的最大和，可以得到表达式 \(dp[i]=max(nums[i],\ dp[i-1]+nums[i])\)。(当然可以直接把原数组当dp数组用，但为了使代码易读还是新建了dp数组)

下面介绍一种直接遍历累加的方法：每次将要累加当前值时，先判断之前已经累加的和是否为负数，如果为负数，当前值加上一个负数只会比自身更小，不如不加，直接重置之前的累加和为0；如果为正数，则可以直接在当前值上加上累加和。这种方法本质上和动态规划是一样的。

分治法：将求当前数组中的最大子数组和这一问题分解为，求出左半边数组中的最大子数组和leftMax、右半边数组中的最大子数组和rightMax、包含左右分割点的中间数组中的最大子数组和midMax，这三者中的最大值即为问题的解。复杂度为\(O(NlogN)\)。

代码实现

Java

动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

遍历累加

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 先判断累加和是否为负数，是则重置为0
            sum = Math.max(sum, 0);
            sum += nums[i];
            max = Math.max(max, sum);
        }

        return max;
    }
}

分治法

class Solution {
    public int maxSubArray(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }

    private int divide(int[] nums, int left, int right) {
        // 递归边界，数组中只剩一个数
        if (right == left) {
            return nums[left];
        }

        int mid = (left + right) / 2;

        // 中间数组必须包含左数组的右端点和右数组的左端点
        int leftSum = nums[mid], rightSum = nums[mid + 1];
        int sum = 0;
        int i = mid;
        while (i >= left) {
            sum += nums[i--];
            leftSum = Math.max(leftSum, sum);
        }
        sum = 0;
        i = mid + 1;
        while (i <= right) {
            sum += nums[i++];
            rightSum = Math.max(rightSum, sum);
        }
		
        int midMax = leftSum + rightSum;
        int leftMax = divide(nums, left, mid);
        int rightMax = divide(nums, mid + 1, right);

        return Math.max(midMax, Math.max(leftMax, rightMax));
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = nums[0]
  let sum = nums[0]

  for (let i = 1; i < nums.length; i++) {
    sum = sum < 0 ? nums[i] : sum + nums[i]
    max = Math.max(sum, max)
  }

  return max
}