Maximum Subarray

描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum = 6.

分析

最大连续子序列和,非常经典的题。

当我们从头到尾遍历这个数组的时候,对于数组里的一个整数,它有几种选择呢?它只有两种选择: 1、加入之前的SubArray;2. 自己另起一个SubArray。那什么时候会出现这两种情况呢?

如果之前SubArray的总体和大于0的话,我们认为其对后续结果是有贡献的。这种情况下我们选择加入之前的SubArray

如果之前SubArray的总体和为0或者小于0的话,我们认为其对后续结果是没有贡献,甚至是有害的(小于0时)。这种情况下我们选择以这个数字开始,另起一个SubArray。

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

f[j]=max{f[j1]+S[j],S[j]},1jnf[j] = \max\left{f[j-1]+S[j],S[j]\right}, 1 \leq j \leq n

target=max{f[j]},1jntarget = \max\left{f[j]\right}, 1 \leq j \leq n

解释如下:

  • 情况一,S[j]不独立,与前面的某些数组成一个连续子序列,则最大连续子序列和为f[j-1]+S[j]。
  • 情况二,S[j]独立划分成为一段,即连续子序列仅包含一个数S[j],则最大连续子序列和为S[j]。
    其他思路:

  • 思路2:直接在i到j之间暴力枚举,复杂度是O(n^3)

  • 思路3:处理后枚举,连续子序列的和等于两个前缀和之差,复杂度O(n^2)。
  • 思路4:分治法,把序列分为两段,分别求最大连续子序列和,然后归并,复杂度O(nlog n)
  • 思路5:把思路2O(n^2)的代码稍作处理,得到O(n)的算法
  • 思路6:当成M=1的最大M子段和

    动规

  1. // Maximum Subarray
  2. // 时间复杂度O(n),空间复杂度O(1)
  3. public class Solution {
  4. public int maxSubArray(int[] nums) {
  5. int maxLocal = nums[0];
  6. int global = nums[0];
  7. for (int i = 1; i < nums.length; ++i) {
  8. maxLocal = Math.max(nums[i], nums[i] + maxLocal);
  9. global = Math.max(global, maxLocal);
  10. }
  11. return global;
  12. }
  13. }

思路5

  1. // Maximum Subarray
  2. // 时间复杂度O(n),空间复杂度O(n)
  3. public class Solution {
  4. public int maxSubArray(int[] nums) {
  5. return mcss(nums, 0, nums.length);
  6. }
  7. // 思路5,求最大连续子序列和
  8. private static int mcss(int[] nums, int begin, int end) {
  9. final int n = end - begin;
  10. int[] sum = new int[n + 1]; // 前n项和
  11. int result = Integer.MIN_VALUE;
  12. int cur_min = sum[0];
  13. for (int i = 1; i <= n; i++) {
  14. sum[i] = sum[i - 1] + nums[begin + i - 1];
  15. }
  16. for (int i = 1; i <= n; i++) {
  17. result = Math.max(result, sum[i] - cur_min);
  18. cur_min = Math.min(cur_min, sum[i]);
  19. }
  20. return result;
  21. }
  22. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dp/maximum-subarray.html