连续子数组的最大和

浏览数：21 / 时间：2015年06月08日

题目：输入一个整型数组，数组里有正数和负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

实现：

bool g_InvalidInput=false;

int FindGreatestSumOfSubArray(int *pData,int nLength)
{
    if((pData==NULL)||(nLength<=0))
    {
        g_InvalidInput=true;
        return 0;
    }
    
    g_InvalidInput=false;
    
    int nCurSum=0;
    int nGreatestSum=0x80000000;
    for(int i=0;i<nLength;++i)
    {
        if(nCurSum<=0)
            nCurSum=pData[i];
        else
            nCurSum+=pData[i];
            
        if(nCurSum>nGreatestSum)
            nGreatestSum=nCurSum;
    }
    
    return nGreatestSum;
}

本文出自 “仙路千叠惊尘梦” 博客，请务必保留此出处http://secondscript.blog.51cto.com/9370042/1586349

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

连续子数组的最大和