Maximum Subarray II

Question

  1. Given an array of integers,
  2. find two non-overlapping subarrays which have the largest sum.
  4. The number in each subarray should be contiguous.
  6. Return the largest sum.
  8. Example
  9. For given [1, 3, -1, 2, -1, 2],
  10. the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2],
  11. they both have the largest sum 7.
  13. Note
  14. The subarray should contain at least one number
  16. Challenge
  17. Can you do it in time complexity O(n) ?

题解

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

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return: An integer denotes the sum of max two non-overlapping subarrays
  5.      */
  6.     public int maxTwoSubArrays(ArrayList<Integer> nums) {
  7.         // -1 is not proper for illegal input
  8.         if (nums == null || nums.isEmpty()) return -1;
  10.         int size = nums.size();
  11.         // get max sub array forward
  12.         int[] maxSubArrayF = new int[size];
  13.         forwardTraversal(nums, maxSubArrayF);
  14.         // get max sub array backward
  15.         int[] maxSubArrayB = new int[size];
  16.         backwardTraversal(nums, maxSubArrayB);
  17.         // get maximum subarray by iteration
  18.         int maxTwoSub = Integer.MIN_VALUE;
  19.         for (int i = 0; i < size - 1; i++) {
  20.             // non-overlapping
  21.             maxTwoSub = Math.max(maxTwoSub, maxSubArrayF[i] + maxSubArrayB[i + 1]);
  22.         }
  24.         return maxTwoSub;
  25.     }
  27.     private void forwardTraversal(List<Integer> nums, int[] maxSubArray) {
  28.         int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
  29.         int size = nums.size();
  30.         for (int i = 0; i < size; i++) {
  31.             minSum = Math.min(minSum, sum);
  32.             sum += nums.get(i);
  33.             maxSub = Math.max(maxSub, sum - minSum);
  34.             maxSubArray[i] = maxSub;
  35.         }
  36.     }
  38.     private void backwardTraversal(List<Integer> nums, int[] maxSubArray) {
  39.         int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
  40.         int size = nums.size();
  41.         for (int i = size - 1; i >= 0; i--) {
  42.             minSum = Math.min(minSum, sum);
  43.             sum += nums.get(i);
  44.             maxSub = Math.max(maxSub, sum - minSum);
  45.             maxSubArray[i] = maxSub;
  46.         }
  47.     }
  48. }

源码分析

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

复杂度分析

前向和后向搜索求得最大子数组和，时间复杂度 O(2n)=O(n), 空间复杂度 O(n). 遍历子数组和的数组求最终两个子数组和的最大值，时间复杂度 O(n). 故总的时间复杂度为 O(n), 空间复杂度 O(n).