Lintcode 41,42 - Maximum Subarray I,II

Related: Lintcode 43 - Maximum Subarray III
Lintcode - Maximum Subarray II - 雯雯熊孩子 - 博客频道 - CSDN.NET

Given an array of integers, find two non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

 Notice

The subarray should contain at least one number

Example

For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

分层两段，左边和右边分别计算max subarray，然后两边加起来最大的就是结果。
思路和股票买卖III一样：

分层两段，左边和右边分别计算max subarray，然后两边加起来最大的就是结果。

这道题目里没有明确说一定要两段（比如一段可不可以，比如左边没有值，右边有一段），但是实际结果是一段是不可以的。。

   public int maxTwoSubArrays(ArrayList<Integer> nums) {
        int[] left = new int[nums.size()];

        int localMax = 0;
        int globalMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            localMax = Math.max(nums.get(i), localMax + nums.get(i));
            globalMax = Math.max(localMax, globalMax);
            left[i] = globalMax;
        }
        
        localMax = 0;
        globalMax = Integer.MIN_VALUE;
        int result = Integer.MIN_VALUE;
        for (int i = nums.size()-1; i >= 0; i--) {
            if (i < nums.size()-1) {
                result = Math.max(result, left[i] + globalMax);
            }
            localMax = Math.max(nums.get(i), localMax + nums.get(i));
            globalMax = Math.max(localMax, globalMax);
        }
        return result;
    }

https://www.cnblogs.com/Dylan-Java-NYC/p/6406168.html

是Maximum Subarray的进阶版. 

可以建立left 保存从左向右 时 到i的最大subarray. right保存从右向左时的到i的最大subarray.

最后res 始终用left[i] + right[i+1]来保持最大.

• 类似题是[Best Time to Buy and Sell Stock III]
• 找两个区间，和最大，则一定存在一个分割线，分割线左右两边分别转化为求一个子数组最大，即[Maximum Subarray I]
• 从左往右枚举一遍分割线求出Maximum Subarray，再从右往左枚举一遍分割线求出Maximum Subarray 这样时间复杂度是O(n)
• 如果从左往右枚举一次分割线，每次左右分别求maximum Subarray，过程中是有浪费的，时间复杂度是O(n^2)

https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73087

前向搜索和逆向搜索我们使用私有方法实现，可读性更高。注意是求非重叠子数组和，故求maxTwoSub时i 的范围为0, size - 2, 前向数组索引为 i, 后向索引为 i + 1.

严格来讲这道题这道题也可以不用动规来做，这里还是采用经典的动规解法。Maximum Subarray 中要求的是数组中最大子数组和，这里是求不相重叠的两个子数组和的和最大值，做过买卖股票系列的题的话这道题就非常容易了，既然我们已经求出了单一子数组的最大和，那么我们使用隔板法将数组一分为二，分别求这两段的最大子数组和，求相加后的最大值即为最终结果。隔板前半部分的最大子数组和很容易求得，但是后半部分难道需要将索引从0开始依次计算吗？NO!!! 我们可以采用从后往前的方式进行遍历，这样时间复杂度就大大降低了。

    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // -1 is not proper for illegal input
        if (nums == null || nums.isEmpty()) return -1;

        int size = nums.size();
        // get max sub array forward
        int[] maxSubArrayF = new int[size];
        forwardTraversal(nums, maxSubArrayF);
        // get max sub array backward
        int[] maxSubArrayB = new int[size];
        backwardTraversal(nums, maxSubArrayB);
        // get maximum subarray by iteration
        int maxTwoSub = Integer.MIN_VALUE;
        for (int i = 0; i < size - 1; i++) {
            // non-overlapping
            maxTwoSub = Math.max(maxTwoSub, maxSubArrayF[i] + maxSubArrayB[i + 1]);
        }

        return maxTwoSub;
    }

    private void forwardTraversal(List<Integer> nums, int[] maxSubArray) {
        int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            minSum = Math.min(minSum, sum);
            sum += nums.get(i);
            maxSub = Math.max(maxSub, sum - minSum);
            maxSubArray[i] = maxSub;
        }
    }

    private void backwardTraversal(List<Integer> nums, int[] maxSubArray) {
        int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
        int size = nums.size();
        for (int i = size - 1; i >= 0; i--) {
            minSum = Math.min(minSum, sum);
            sum += nums.get(i);
            maxSub = Math.max(maxSub, sum - minSum);
            maxSubArray[i] = maxSub;
        }
    }

https://www.jianshu.com/p/65c49a036331

http://geekilyyours.blogspot.com/2014/09/maximum-subsequence-sum.html

    public static void maximumContSubSeq(int[] a) {

        int sum[] = new int[a.length]; // Sum at every element

        sum[0] = a[0];

        int max = 0;

        for (int i = 1; i < a.length; i++) {

            sum[i] = Math.max(sum[i - 1] + a[i], a[i]);

            if(sum[i-1]+a[i]>a[i]){

                sum[i] = sum[i - 1] + a[i];

            }

            if (max < sum[i]) {

                max = sum[i];

            }

        }

        System.out.println(max);

    }

下一个问题就是如何找到两个不重合的连续子数组，使其和最大了。

基于上一题，我们发现可以将整个数组划分为两个，然后在左右两边分别找到相应最大和的子数组，那么这两个连续子数组就是对于这个数组划分而言的最优解了。于是，这个问题就简化成了找到一个数组的划分点，使得左右两边最优解之和最大了，其中求左右两边最优解这一部分已经被我们在上一题中解决掉了。

基本思路理清楚之后，具体实现就很直接了：先从左往右扫一遍，记录下从数组起始位置到当前为止的连续子数组的最大和，再从右往左扫一遍，记录下从数组末尾位置到当前位置的连续子数组的最大和，最后结合这两部分信息，找到全局最优解

其中关于left值得注意一下，为了避免单独处理第一个元素，我们在前面加了一个pseudo head，所以left[i]代表的是数组范围[0,i)内的最大子数组之和。而由于right的pseudo head是加在了末尾，所以代表的是数组范围[i,n)内的最大子数组之和。

其实，我们可以进一步对代码进行优化，即将求right和globalMaxSum这两个步骤合并，那么我们就不需要记录整个right数组，用与上一题中的localMaxSum代替就行了。但为了代码的逻辑清晰和可读性，就不做此优化了。这里的时间复杂度也很清楚，扫了三遍数组，就是$O\left(N\right)$了。

http://www.jiuzhang.com/solutions/maximum-subarray-ii/

这个题的思路是，因为 两个subarray 一定不重叠

所以必定存在一条分割线

分开这两个 subarrays

所以 最后的部分里：

  max = Integer.MIN_VALUE;

        for(int i = 0; i < size - 1; i++){

            max = Math.max(max, left[i] + right[i + 1]);

        }

        return max;

这里是在枚举 这条分割线的位置

然后 left[] 和 right[] 里分别存的是，某个位置往左的 maximum subarray 和往右的 maximum subarray

    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        int size = nums.size();
        int[] left = new int[size];
        int[] right = new int[size];
        int sum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < size; i++){
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(sum, minSum);
            left[i] = max;
        }
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for(int i = size - 1; i >= 0; i--){
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(sum, minSum);
            right[i] = max;
        }
        max = Integer.MIN_VALUE;
        for(int i = 0; i < size - 1; i++){
            max = Math.max(max, left[i] + right[i + 1]);
        }
        return max;
    }

https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73087

http://blog.hyoung.me/cn/2017/02/maximum-subarray/

基于上一题，我们发现可以将整个数组划分为两个，然后在左右两边分别找到相应最大和的子数组，那么这两个连续子数组就是对于这个数组划分而言的最优解了。于是，这个问题就简化成了找到一个数组的划分点，使得左右两边最优解之和最大了，其中求左右两边最优解这一部分已经被我们在上一题中解决掉了。

基本思路理清楚之后，具体实现就很直接了：先从左往右扫一遍，记录下从数组起始位置到当前为止的连续子数组的最大和，再从右往左扫一遍，记录下从数组末尾位置到当前位置的连续子数组的最大和，最后结合这两部分信息，找到全局最优解。代码如下

其中关于left值得注意一下，为了避免单独处理第一个元素，我们在前面加了一个pseudo head，所以left[i]代表的是数组范围[0,i)内的最大子数组之和。而由于right的pseudo head是加在了末尾，所以代表的是数组范围[i,n)内的最大子数组之和。

其实，我们可以进一步对代码进行优化，即将求right和globalMaxSum这两个步骤合并，那么我们就不需要记录整个right数组，用与上一题中的localMaxSum代替就行了。但为了代码的逻辑清晰和可读性，就不做此优化了。这里的时间复杂度也很清楚，扫了三遍数组，就是$O\left(N\right)$了

int maxTwoSubArrays(vector<int> nums) {

int n = nums.size();



int localMaxSum = 0;

// left[i] represents max subarray in nums[0,i)

vector<int> left(n + 1, INT_MIN);

for (int i = 0; i < n; ++i) {

localMaxSum += nums[i];

left[i+1] = max(left[i], localMaxSum);

localMaxSum = max(0, localMaxSum);

}



localMaxSum = 0;

// right[i] represents max subarray in nums[i,n-1]

vector<int> right(n + 1, INT_MIN);

for (int i = n - 1; i >= 0; --i) {

localMaxSum += nums[i];

right[i] = max(right[i+1], localMaxSum);

localMaxSum = max(0, localMaxSum);

}



int globalMaxSum = INT_MIN;

for (int i = 1; i < n; ++i)

globalMaxSum = max(globalMaxSum, left[i] + right[i]);



return globalMaxSum;

}

LintCode 上面这一系列的衍生题目还是相当的有趣，涉及到了数组操作的常用技巧，如前缀和等，还有不少关于动态规划的分析、优化，其变种之多也使得完成这一系列题型可以更加系统性地掌握这些技巧并进行拓展延伸
Maximum Subarray I (LintCode 41）

Given an array of integers, find a contiguous subarray which has the largest sum.

 Notice

The subarray should contain at least one number.

Example

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

最暴力的思路显然就是枚举了。枚举方式可以用两层循环，第一层假设子数组起始位置从nums[0]到nums[n-1]，然后第二层就从连续子数组包含1个数一直到n个数。这种暴力枚举的时间复杂度为 $O\left(N^2\right)$，显然不是我们想要的，代码就略过不写了。

前缀和（Prefix Sum）

看到这个题目时，第一个思路就是利用prefix sum。基本思路就是：若以nums[i]为子数组最后一个元素，那么这个子数组和的最大值就是这段数组之和与最小前缀数组和的差值，即

$$\text{sum[i]}-argmi{n}_j\text{sum[j]},\text{for}j<i$$

同时，再维护一个全局最大和就行了。

基本思路理清后，就可以考虑具体实现了。首先是sum，用一个变量进行维护，不断累加即可。而最小前缀数组和可以通过一个数组维护，比如minSum[i]存的是子数组nums[0:i]中值最小的前缀和。其本质是一种最简单的动态规划，其状态转移方程为

1	minSum[i] = min(minSum[i-1], sum[i])

仔细观察下，我们就能发现这里可以进行内存优化，那就是，既然我们只是利用到了前一个值，就没有必要保留整个minSum数组，用一个minSum变量动态维护当前最小值就可以了，状态转移方程就可以简化为

1	minSum = min(minSum, sum[i])

这也是动态规划中常用的内存优化技巧。完整代码如下

1 2 3 4 5 6 7 8 9

int maxSubArray(vector<int> nums) { int sum = 0, globalMaxSum = INT_MIN, minSum = 0; for (int num : nums) { sum += num; globalMaxSum = max(globalMaxSum, sum - minSum); minSum = min(minSum, sum); } return globalMaxSum; }

其中，minSum的初始值设为0值得注意一下。很显然，只是扫了一遍整个数组，所以时间复杂度为$O\left(N\right)$。

Kadane’s Algorithm

更进一步研究整个算法，可以发现我们其实并不需要单独维护滚动数组加和sum以及最小前缀和minSum，可以把他们合并为localMaxSum数组。其中，localMaxSum[i]表示的是以nums[i]为子数组中最后一个元素时的子数组最大和。同样的，我们可以进行优化，仅用一个变量来记录即可。更改后的代码如下

1 2 3 4 5 6 7 8 9

int maxSubArray(vector<int> nums) { int localMaxSum = 0, globalMaxSum = INT_MIN; for (int num : nums) { localMaxSum += num; globalMaxSum = max(globalMaxSum, localMaxSum); localMaxSum = max(0, localMaxSum); } return maxSum; }

这就是 Kadane’s Algorithm 了，其背后的关键点就在于当发现localMaxSum为负之后，对于下一个元素而言，最佳策略就是扔掉前面所有的元素了，重新以它自身为子数组起始点。

这里，使用数组形式来观察可能更好理解，比如当localMaxSum[i] < 0时，意味着以元素nums[i]结尾的子数组最大和为负，对于nums[i+1]这个元素而言，若要往前拓展，即至少包含nums[i]，只会带来更差的结果，所以要扔掉前面的所有元素，加和从0开始。

http://www.lintcode.com/en/problem/maximum-subarray-iii/

Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

The number in each subarray should be contiguous.

Return the largest sum.

 Notice

The subarray should contain at least one number

Example

Given [-1,4,-2,3,-2,3], k=2, return 8

接下来就是扩展到k个不重合连续子数组最大和的问题了。

类似于上一题中将整个数组切分为二，然后分别找局部最优解，在这里，我们自然而然可以使用相同的技巧：同样把整个数组切分为二，右边依旧是找一个连续子数组的最大和，而左边则为找k-1个不重合连续子数组的最大和。如此一来，这就是一个典型的动态规划问题了。代码如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

int maxSubArray(vector<int> nums, int k) { int n = nums.size(); if (n < k) return 0; vector<vector<int>> globalMaxSum(k + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= k; ++i) { for (int j = i; j <= n; ++j) { globalMaxSum[i][j] = INT_MIN; int localMaxSum = 0; for (int p = j - 1; p >= i - 1; --p) { localMaxSum += nums[p]; globalMaxSum[i][j] = max(globalMaxSum[i][j], globalMaxSum[i-1][p] + localMaxSum); localMaxSum = max(0, localMaxSum); } } } return globalMaxSum[k][n]; }

代码十分简练，不过也有几个地方需要注意一下。

首先，与上一题中我们往left中加了一个pseudo head类似，这里globalMaxSum[i][j]代表着在数组范围[0,j)中i个不重合连续子数组最大和，并不包括元素nums[j]。

第二，第二层循环中j的取值从i开始。因为每个子数组至少包含一个元素，所以第i个子数组得从nums[i-1]开始搜索，又由于pseudo head的存在，j的起始位置就是i-1+1 = i了。第三层循环中切分点p也易出错，它对应的直接是数组中的位置，因此它的最小值应该为i-1，而最大值为j-1。

第三，在第三层循环中，我们是选择从右往左进行搜索，其实就是我们在上一题中没有做的优化，将右边搜索和全局搜索结合起来了。

这种算法的时间复杂度通过三层循环来看，也能比较简单地推出来，即$O\left(k{N}^2\right)$，但跟我们在上一题中求出的时间复杂度$O\left(N\right)$并不相符，这就引出了我们下面的优化过程。

通过进一步分析上面代码我们可以发现，在计算globalMaxSum[i][j]时，我们仅仅利用了globalMaxSum[i-1]的信息，那么我们有没有办法利用更多的信息，如globalMaxSum[i][j-1]呢？

我们发现，对于globalMaxSum[i][j]而言，只有两种选择，要么包括nums[j-1],要么不包括nums[j-1]，而后者策略的结果就是前面计算的globalMaxSum[i][j-1]。因此，我们只需要关注如何高效计算出包括nums[j-1]时的结果。

我们可以维护一个localMaxSum数组，其中localMaxSum[j]记录着包括nums[j-1]时的i个不重合连续子数组的最大和。那么其状态转移方程也比较好推出来，即

localMaxSum[j] = max(localMaxSum[j-1], globalMaxSum[i-1][j-1]) + nums[j-1]

对于前一种策略而言，即将nums[j-1]并入到localMaxSum[j-1]的最后一个子数组中，使得localMaxSum[j]依旧维护着i个子数组；对于后一种策略，即将nums[j-1]作为一个新的子数组与前面k-1个最优子数组组成新的最优解。

同时，我们也可以注意到，其实并不需要维护整个数组，用一个变量动态维护即可。代码如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int maxSubArray(vector<int> nums, int k) { int n = nums.size(); if (n < k) return 0; vector<vector<int>> globalMaxSum(k + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= k; ++i) { int localMaxSum = INT_MIN; for (int j = i; j <= n; ++j) { localMaxSum = max(localMaxSum, globalMaxSum[i-1][j-1]) + nums[j-1]; if (i == j) globalMaxSum[i][j] = localMaxSum; else globalMaxSum[i][j] = max(localMax, globalMaxSum[i][j-1]); } } return globalMaxSum[k][n]; }

这里唯一需要注意的地方就是当i==j时的特殊情况，这意味着从i个元素中选出i个子数组了，有且只有一种组合。在这里并不能直接去与globalMaxSum[i][j-1]相比较，首先，这种情况不应该存在，其次，由于我们初始值为0，当数组和为负时，使用max来判断就会给出错误的结果。当然我们也可以将这些「不存在」的情况初始化为INT_MIN，这样就没有问题了。很容易计算，通过优化，时间复杂度被降到了$O\left(kN\right)$。

Read full article from Lintcode - Maximum Subarray II - 雯雯熊孩子 - 博客频道 - CSDN.NET