leetcode题解-53.最大子序和

题目

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 ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

分析

题目意思应该比较清晰了，我们也能很快想到一种方法，那就是计算所有可能的组合，然后比较所有组合的结果，选出结果最大的那个即可。这确实是一个可行的犯法，但是当数组越来越大时，其组合的可能性也越来越多，这显然是一个很低效的算法。那么有没有更好的办法呢？有! 思路也很简单，我们把整个序列分为两部分，前面一部分是已知最大子序列和的，后面的是还没有参与计算最大子序列和的。既然我们已经知道前面部分的最大子序列和，如果前部分最大子序列和小于0，则加上一个数，将会小于这个数。所以当前最大数就是当前数，否则的话，当前最大数是前部分的序列和加上该数。再将当前数与之前的最大和比较，取较大值即可，直到遍历所有数，找到最终的最大序列和。

还是以题目中给出的输入为例，首先，最大子序列和为-2，-2小于0，因此当前最大数为1，它与-2比较,1更大，因此最大子序列和为1；此时1大于0，因此需要加上后面的-3，因此当前最大子序列和为-2，但是它仍然比之前的最大子序列和1小，因此最大子序列和仍然为1，以此循环，最终会得到该数组的最大子序列和为6.

我们可以看到这种动态规划的解答方法的时间复杂度为O(N)。

代码

c语言实现的代码如下：

int maxSubArray(int* nums, int numsSize) {
    if(NULL == nums)
        return 0;
    int curMax = 0;
    int maxSum = INT_MIN;  //初始最大和赋为int的最小值
    int loop  = 0;
    for(loop;loop < numsSize;loop++)
    {
        if(curMax > 0) 
            ////如果当前最大和大于0，则当前最大和需要加上当前值
            curMax = curMax+nums[loop];
        else
            //如果当前最大和小于0，则当前最大和重新计算
            curMax = nums[loop];
        if(curMax > maxSum)
            //如果当前最大和大于前面的最大和，则更新最大和的值
            maxSum = curMax;
    }
    return maxSum;

}