53.MaximumSubarray-创新互联

53. Maximum Subarray

成都创新互联公司主营振兴网站建设的网络公司,主营网站建设方案,app软件定制开发,振兴h5小程序开发搭建,振兴网站营销推广欢迎振兴等地区企业咨询

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;
}

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


名称栏目:53.MaximumSubarray-创新互联
当前路径:http://scyanting.com/article/cdojjp.html