189 8069 5689
53. Maximum Subarray
创新互联建站主要从事成都网站制作、做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务无为,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220
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型的任何负数都可存入。int maxSubArray(int* nums, int numsSize)
{
int cnt = 0;
int max = INT_MIN;
int sum = 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;
}
}
return max;
}