一、题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

翻译：

给你一个整数型数组nums，找出连续的子数组(长度至少为1)使得其和最大，返回这个最大值。

举例：

输入：[-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：子数组[4,-1,2,1] 具有最大和为6

跟进：

如果你找到了O(n)的解决方案，尝试使用分治方法来编写另一个解决方案，这是更微妙的解法。

二、分析

(一)暴力解法

暴力方式就是在数组nums长度范围内以任意位置开始计算任意长度的数组，同时始终记录下和最大的那个值，当所有的情况都考虑完后，自然就记录下了最大值。其复杂度为O(n³)。

代码：

 1 int maxSubArray(int* nums, int numsSize) {
 2     int maxSum = nums[0],sum;
 3     for (int i = 0; i < numsSize; i++) {
 4         for (int j = i; j < numsSize; j++) {
 5             sum = 0;
 6             for (int k = i; k <= j; k++)
 7                 sum += nums[k];
 8             if (sum > maxSum)
 9                 maxSum = sum;
10         }
11     }
12     return maxSum;
13 }

(二)优化的暴力解法

方法一在计算数组的和时每次都从开始计算，这在计算过程中存在大量的重复运算，因此很容易超时。因为在以某个起始位置开始逐渐增长长度来计算和时，只需在上次求和的基础上直接计算即可。这样就可以减少大量的重复运算。其复杂度为O(n²)。

代码：

 1 int maxSubArray(int* nums, int numsSize) 
 2 {
 3     int maxSum = nums[0],sum;
 4     for (int i = 0; i < numsSize; i++) 
 5     {
 6         sum = 0;
 7         for (int j = i; j < numsSize; j++) 
 8         {
 9             sum += nums[j];
10             maxSum=sum > maxSum?sum:maxSum;
11         }
12     }
13     return maxSum;
14 }

(三)分治算法

我们在计算时总是希望nums数组能够足够短，因为这样能更好计算。如果长度为1，我们可以直接返回。所以我们总是想把问题分开讨论，这里需要对数组进行细分。此时我们考虑最大的子数组存在的可能位置：

　　　　1.仅在nums数组的左半边；

　　　　2.仅在nums数组的右半边；

　　　　3.跨立nums数组的中间。

对于前两种情况我们可以继续对子数组进行重复调用自身的办法继续细分问题，从而将问题无限减小到可以直接计算，而第3种情况则不能，但我们可以考虑到这种情况下子数组一定是分成两部分：左半边的最大后缀和右半边的最大前缀，因此我们只需要将此时的两边的子数组进行求和即可。

当我们把这三种情况考虑完后，返回最大的那种情况即可。

由于我们进行了二分，但是每次二分我们都需要以线性时间求第三种情况，因此我们的时间复杂度是O(nlogn)。(注意：logn以2为底)

代码：

 1 int maxSubArray(int* nums, int numsSize) {
 2     return maxSubArrayEx(nums,0,numsSize-1);
 3 }
 4 int maxSubArrayEx(int* nums,int left,int right) {
 5     if (left == right)
 6         return nums[left];
 7     int center = (left + right) / 2;
 8     int ml = maxSubArrayEx(nums, left, center);
 9     int mr = maxSubArrayEx(nums, center + 1, right);
10     int mlb = nums[center], lb = nums[center];
11     for (int i = center-1; i >= left; i--) {
12         lb += nums[i];
13         if (lb > mlb)mlb = lb;
14     }
15     int mrb = nums[center+1], rb = nums[center+1];
16     for (int i = center + 2; i <= right; i++) {
17         rb += nums[i];
18         if (rb > mrb)mrb = rb;
19     }
20     int mb = mlb + mrb;
21     return mb > ml ? mb > mr ? mb : mr: ml > mr ? ml : mr;
22 }

注：由于LeetCode的函数与我们的参数不一样，因此我们编写了maxSubArrayEx函数。

(四)统计分析

虽然分治算法已经很快了，但是它依然不是最高效的计算方式。我们再次分析，由于我们不知道nums数组的每一个元素的正负性，因此我们只能作一般性假设。

设S[i]是以下标为i的元素作为结尾的和最大的子数组，虽然这个子数组可能不是所求，但是容易发现最终的答案一定存在其中，他可能是S[j]；

那么S[i+1]=max(S[i]+nums[i+1],nums[i+1])。为什么呢？因为S[i]已经是下标为i的元素结尾的和最大的子数组了，那么再添加nums[i+1]会不会自动是以下标为i+1结尾的和最大的子数组呢？不一定！如果S[i]<0,S[i+1]不应该将前面的加上，也即此时S[i+1]=nums[i+1]，如果S[i]>0,则此时S[i+1]=S[i]+nums[i+1]。注意：我们前面已经假设了S[i]一定是以下标为i个元素结尾的和最大的子数组，这表明S[i+1]一定要以nums[i+1]结尾！

经过以上分析，我们得到了一个递推关系式，这就像数列一样。

S[0]=nums[0]，S[i+1]=max(S[i]+nums[i+1],nums[i+1])。于是我们只需要利用递推关系式计算S[i]再与记录的最大值进行比较即可。这样利用递推关系只需遍历一遍数组即可计算出结果，所以时间复杂度是O(n)。

代码：

1 int maxSubArray(int* nums, int numsSize) {
2     int result=nums[0],sum=nums[0];
3     for(int i=1;i<numsSize;i++)
4     {
5         sum=sum>0?sum+nums[i]:nums[i];
6         result=sum>result?sum:result;
7     }
8     return result;
9 }

同理，如果我们规定P[i]是以下标为i元素作为起点的和最大的子数组，同样可以得到倒着计算的方式。

代码：

1 int maxSubArray(int* nums, int numsSize) {
2     int result=nums[numsSize-1],sum=nums[numsSize-1];
3     for(int i=numsSize-2;i>=0;i--)
4     {
5         sum=sum>0?sum+nums[i]:nums[i];
6         result=sum>result?sum:result;
7     }
8     return result;
9 }

注：此方法也被称为动态规划。