LeetCode OJ 53. 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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

【题目分析】

题目要求我们在给定的一个数组中找出一个数组元素之和最大子数组，并返回最大的和。

【思路】动态规划

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

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

1. 如果sum>=0，就可以和A[i]拼接在一起构成新的sum'。因为不管A[i]多大，加上一个正数总会更大，这样形成一个新的candidate。

2. 反之，如果sum<0，就没必要和A[I]拼接在一起了。因为不管A[i]多小，加上一个负数总会更小。此时由于题目要求数组连续，所以没法保留原sum，所以只能让sum等于从A[i]开始的新的一段数了，这一段数字形成新的candidate。

3. 如果每次得到新的candidate都和全局的max_sum进行比较，那么必然能找到最大的max sum subarray.

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

其实上面的思想是最简单的动态规划的思想，用maxl[i]数组表示包含i元素的子数组的最大和，则动态规划的递推公式为：maxl[i+1] = max(maxl[i]+A[i], A[i+1])，即最大值一定是数组当前元素以及数组当前元素和前一结果之和的最大值。接下来整个问题的最大值就是maxl数组中的最大值。

面的分析过程是一个简单的动态规划，这个算法叫做 Kadane's algorithm，参加维基百科：https://en.wikipedia.org/wiki/Maximum_subarray_problem

时间复杂度：O(n) 空间复杂度：O(1)

【思路2】分而治之

问题解决了，可是发现了下面的拓展，即分治解决。提到分治，思路来了，当前的最大值等于左侧最大值和右侧最大值中较大的。可是，有一点点问题，这个最大值还有可能是横跨左右两侧的啊。。。

于是，在处理两侧的子问题的时候，需要同时分别计算包含最左端元素的最大值（lres）和包含最右端元素的最大值（rres）。这样，当前的最大值就为“左侧最大值（res1）”、“右侧最大值（res2）”、“左侧含最右端元素的最大值（rres1）及右侧包含最左端元素的最大值（lres2）之和”三者的最大值。

而由于lres可分为只在左侧和也包含右侧两种情况：

左侧含最左端元素的最大值（lres1）
左侧元素之和加右侧含最左端元素的最大值（all1+lres2）

含最右端元素的最大值同理，即lres = max(lres1, all1 + lres2)和rres = max(rres2, all2 + rres1)。

问题得以解决。至于时间复杂度，个人认为，是n/2 + n/4 + n/8 + ... = O(n)。

【java代码】动态规划

 1 public class Solution {
 2     public int maxSubArray(int[] nums) {
 3         if(nums == null || nums.length == 0) return 0;
 4         
 5         int length = nums.length;
 6         if (length == 1){
 7             return nums[0];
 8         }
 9         int currentsum = nums[0];
10         int maxsum = nums[0];
11         for (int i = 1; i < length; i++){
12             if (currentsum >= 0){
13                 currentsum += nums[i];
14             }
15 
16             else{
17                 currentsum = nums[i];
18             }
19 
20             maxsum = maxsum > currentsum ? maxsum : currentsum;
21         }
22 
23         return maxsum;
24     }
25 }

【C++代码】分而治之

 1 class Solution{
 2  public:
 3       int maxSubArray(int A[], int n){
 4           int res, lres, rres, all;
 5           maxSubArray(A, 0, n - 1, res, lres, rres, all);
 6           return res;
 7       }
 8  private:
 9      void maxSubArray(int A[], int l, int r, int &res, int &lres, int &rres, int &all){
10          if(l == r)
11          {
12              res = lres = rres = all = A[l];
13              return;
14          }
15  
16          int m = (l + r) / 2;
17          int res1, lres1, rres1, all1, res2, lres2, rres2, all2;
18  
19          maxSubArray(A, l, m, res1, lres1, rres1, all1);
20          maxSubArray(A, m + 1, r, res2, lres2, rres2, all2);
21  
22          res = max(max(res1, res2), rres1 + lres2);
23          lres = max(lres1, all1 + lres2);
24          rres = max(rres2, all2 + rres1);
25          all = all1 + all2;
26      }
27  };