53.Maximum Subarray(最大子序和)

武培轩 2020年02月06日 61次浏览

题目描述

给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。

例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4],
连续子序列 [4,-1,2,1] 的和最大,为 6。

扩展练习:

若你已实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

思路

思路一:

maxSum 必然是以nums[i](取值范围为nums[0] ~ nums[n-1])结尾的某段构成的,也就是说maxSum的candidate必然是以nums[i]结果的。如果遍历每个candidate,然后进行比较,那么就能找到最大的maxSum了。

假设把nums[i]之前的连续段叫做sum。可以很容易想到:

  1. 如果sum>=0,就可以和nums[i]拼接在一起构成新的sum。因为不管nums[i]多大,加上一个正数总会更大,这样形成一个新的candidate。
  2. 反之,如果sum<0,就没必要和nums[i]拼接在一起了。因为不管nums[i]多小,加上一个负数总会更小。此时由于题目要求数组连续,所以没法保留原sum,所以只能让sum等于从nums[i]开始的新的一段数了,这一段数字形成新的candidate。
  3. 如果每次得到新的candidate都和全局的maxSum进行比较,那么必然能找到最大的max sum subarray.

在循环过程中,用maxSum记录历史最大的值。从nums[0]到nums[n-1]一步一步地进行。

思路二:

遍历array,对于每一个数字,我们判断,(之前的sum + 这个数字) 和 (这个数字) 比大小,如果(这个数字)自己就比 (之前的sum + 这个数字) 大的话,那么说明不需要再继续加了,直接从这个数字,开始继续,因为它自己已经比之前的sum都大了。

反过来,如果 (之前的sum + 这个数字)大于 (这个数字)就继续加下去。

利用动态规划做题。
只遍历数组一遍,当从头到尾部遍历数组A, 遇到一个数有两种选择 (1)加入之前subArray (2)自己另起一个subArray

设状态S[i], 表示以A[i]结尾的最大连续子序列和,状态转移方程如下:

S[i] = max(S[i-1] + A[i],A[i])

从状态转移方程上S[i]只与S[i-1]有关,与其他都无关,因此可以用一个变量来记住前一个的最大连续数组和就可以了。这样就可以节省空间了。

代码实现

package Array;

/**
 * 53.Maximum Subarray(最大子序和)
 * 给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。
 * 例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4],
 * 连续子序列 [4,-1,2,1] 的和最大,为 6。
 */
public class Solution53 {
    public static void main(String[] args) {
        Solution53 solution53 = new Solution53();
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(solution53.maxSubArray(arr));
    }

    /**
     * maxSum 必然是以nums[i](取值范围为nums[0] ~ nums[n-1])结尾的某段构成的,也就是说maxSum的candidate必然是以nums[i]结果的。如果遍历每个candidate,然后进行比较,那么就能找到最大的maxSum了。
     * 假设把nums[i]之前的连续段叫做sum。可以很容易想到:
     * 1. 如果sum>=0,就可以和nums[i]拼接在一起构成新的sum。因为不管nums[i]多大,加上一个正数总会更大,这样形成一个新的candidate。
     * 2. 反之,如果sum<0,就没必要和nums[i]拼接在一起了。因为不管nums[i]多小,加上一个负数总会更小。此时由于题目要求数组连续,所以没法保留原sum,所以只能让sum等于从nums[i]开始的新的一段数了,这一段数字形成新的candidate。
     * 3. 如果每次得到新的candidate都和全局的maxSum进行比较,那么必然能找到最大的max sum subarray.
     * 在循环过程中,用maxSum记录历史最大的值。从nums[0]到nums[n-1]一步一步地进行。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int sum = 0; //或者初始化为  sum = INT_MIN 也OK。
        int maxSum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (sum >= 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
        return maxSum;
    }

    /**
     * 遍历array,对于每一个数字,我们判断,(之前的sum + 这个数字) 和 (这个数字) 比大小,如果(这个数字)自己就比 (之前的sum + 这个数字) 大的话,那么说明不需要再继续加了,直接从这个数字,开始继续,因为它自己已经比之前的sum都大了。
     * 反过来,如果 (之前的sum + 这个数字)大于 (这个数字)就继续加下去。
     * 利用动态规划做题。
     * 只遍历数组一遍,当从头到尾部遍历数组A, 遇到一个数有两种选择 (1)加入之前subArray (2)自己另起一个subArray
     * 设状态S[i], 表示以A[i]结尾的最大连续子序列和,状态转移方程如下:
     * S[i] = max(S[i-1] + A[i],A[i])
     * 从状态转移方程上S[i]只与S[i-1]有关,与其他都无关,因此可以用一个变量来记住前一个的最大连续数组和就可以了。
     * 这样就可以节省空间了。
     * 时间复杂度:O(n)     空间复杂度:O(1)
     */
    public int maxSubArray_2(int[] nums) {
        int sum = 0; //或者初始化为  sum = INT_MIN 也OK。
        int maxSum = nums[0];
        //动态规划
        for (int i = 0; i < nums.length; i++) {
            sum = Math.max(sum + nums[i], nums[i]);
            maxSum = Math.max(sum, maxSum);
        }
        return maxSum;
    }
}