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.


题意：

根据给定的数组，查找和最大的字串。


使用"Kadane算法"查找最大和字串。


解题：

1）定义变量Max来保存最大和。定义sum来保存中间值的和。

2）数组连续几个值的和如果为负数，也就意味着再往负数上加正数就没有意义了，加上的和肯定不会大于加上数的值。此时重新开始计算联系元素和即可。

3）如果数组为全负元素，那么取出最大值即可。

if(sum<=0){sum=0;}作用保证重新计数时，是从零开始的。if(sum<=0){sum=*(nums+cnt);}没有置零而是置为当前值，是为了防止全负数组时，能把最大的值存入Max变量中。Max起始置为INT_MIN保证了int型的任何负数都可存入。


intmaxSubArray(int*nums,intnumsSize){intcnt=0;intmax=INT_MIN;intsum=0;for(cnt=0;cnt<numsSize;cnt++){if(sum<=0){sum=0;}sum=sum+*(nums+cnt);if(sum<=0){sum=*(nums+cnt);}if(sum>max){max=sum;}}returnmax;}