leetcode题解-53.最大子序和

原题地址

https://leetcode.com/problems/maximum-subarray/

题目-53. Maximum Subarray

给定一个整数数组 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语言实现的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

运行时间

Runtime: 4 ms

守望 wechat
关注公众号[编程珠玑]获取更多原创技术文章
出入相友,守望相助!