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

题目要求最大连续子数组的和，这里比较直接的思路是用动态规划，利用分治思想把问题进行拆分，我们用两个变量分别记录当前和与最大和，如果当前和是负数，那么就可以把它舍弃直接用数组中的当前数字代替它即可，因为负数加上之后当前数字比当前数字更小，不如不加，代码如下：

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) 
 4     {
 5         int nCurSum = 0;           //当前和
 6         int nGreatestSum = INT_MIN;  //最大和
 7         for (auto num : nums)
 8         {
 9             nCurSum = max(num, num + nCurSum);
10             nGreatestSum = max(nCurSum, nGreatestSum);
11         }
12         return nGreatestSum;
13     }
14 };

或者是不调用max函数，但是这样做并不能提高速度：

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) 
 4     {
 5         int nCurSum = 0;
 6         int nGreatestSum = INT_MIN;
 7         for (auto num : nums)
 8         {
 9             if (nCurSum <= 0)
10                 nCurSum = num;
11             else
12                 nCurSum += num;
13             if (nCurSum > nGreatestSum)
14                 nGreatestSum = nCurSum;
15         }
16         return nGreatestSum;
17     }
18 };