Maximum Subarray

Question

  1. Given an array of integers,
  2. find a contiguous subarray which has the largest sum.
  4. Example
  5. Given the array [−2,2,−3,4,−1,2,1,−5,3],
  6. the contiguous subarray [4,−1,2,1] has the largest sum = 6.
  8. Note
  9. The subarray should contain at least one number.
  11. Challenge
  12. Can you do it in time complexity O(n)?

题解1 - 贪心

求最大子数组和，即求区间和的最大值，不同子区间共有约 n^2 中可能，遍历虽然可解，但是时间复杂度颇高。

这里首先介绍一种巧妙的贪心算法，用sum表示当前子数组和，maxSum表示求得的最大子数组和。当sum <= 0时，累加数组中的元素只会使得到的和更小，故此时应将此部分和丢弃，使用此时遍历到的数组元素替代。需要注意的是由于有maxSum更新sum, 故直接丢弃小于0的sum并不会对最终结果有影响。即不会漏掉前面的和比后面的元素大的情况。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return: A integer indicate the sum of max subarray
  5.      */
  6.     public int maxSubArray(ArrayList<Integer> nums) {
  7.         // -1 is not proper for illegal input
  8.         if (nums == null || nums.isEmpty()) return -1;
  10.         int sum = 0, maxSub = Integer.MIN_VALUE;
  11.         for (int num : nums) {
  12.             // drop negtive sum
  13.             sum = Math.max(sum, 0);
  14.             sum += num;
  15.             // update maxSub
  16.             maxSub = Math.max(maxSub, sum);
  17.         }
  19.         return maxSub;
  20.     }
  21. }

源码分析

贪心的实现较为巧妙，需要sum和maxSub配合运作才能正常工作。

复杂度分析

遍历一次数组，时间复杂度 O(n), 使用了几个额外变量，空间复杂度 O(1).

题解2 - 动态规划1(区间和)

求最大/最小这种字眼往往都可以使用动态规划求解，此题为单序列动态规划。我们可以先求出到索引 i 的子数组和，然后用子数组和的最大值减去最小值，最后返回最大值即可。用这种动态规划需要注意初始化条件和求和顺序。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return: A integer indicate the sum of max subarray
  5.      */
  6.     public int maxSubArray(ArrayList<Integer> nums) {
  7.         // -1 is not proper for illegal input
  8.         if (nums == null || nums.isEmpty()) return -1;
  10.         int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
  11.         for (int num : nums) {
  12.             minSum = Math.min(minSum, sum);
  13.             sum += num;
  14.             maxSub = Math.max(maxSub, sum - minSum);
  15.         }
  17.         return maxSub;
  18.     }
  19. }

源码分析

首先求得当前的最小子数组和，初始化为0，随后比较子数组和减掉最小子数组和的差值和最大区间和，并更新最大区间和。

复杂度分析

时间复杂度 O(n), 使用了类似滚动数组的处理方式，空间复杂度 O(1).

题解3 - 动态规划2(局部与全局)

这种动规的实现和题解1 的思想几乎一模一样，只不过这里用局部最大值和全局最大值两个数组来表示。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @return: A integer indicate the sum of max subarray
  5.      */
  6.     public int maxSubArray(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.         int[] local = new int[size];
  12.         int[] global = new int[size];
  13.         local[0] = nums.get(0);
  14.         global[0] = nums.get(0);
  15.         for (int i = 1; i < size; i++) {
  16.             // drop local[i - 1] < 0
  17.             local[i] = Math.max(nums.get(i), local[i - 1] + nums.get(i));
  18.             // update global with local
  19.             global[i] = Math.max(global[i - 1], local[i]);
  20.         }
  22.         return global[size - 1];
  23.     }
  24. }

源码分析

由于局部最大值需要根据之前的局部值是否大于0进行更新，故方便起见初始化 local 和 global 数组的第一个元素为数组第一个元素。

复杂度分析

时间复杂度 O(n), 空间复杂度也为 O(n).

Reference