【Data Structure & Algorithm】求子数组的最大和

求子数组的最大和

题目：输入一个整型数组，数组里有正数和负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值，要求时间复杂度为O(n)。例如输入数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

分析：如果不考虑时间复杂度，可以枚举出所有子数组并求其和。但是由于长度为n的数组有O(n²)个子数组；且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n³)。

其实，当加上一个正数时，和会增加；当加上一个负数时，和会减少。如果当前得到的和是一个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然这个负数将会减少接下来的和。

boolFind GreatestSumOfSubArray (int *pData, unsigned int nLength, int &nGreatestSum)

{

       if ((pData ==NULL) || (nLength ==0))

              return false;

       int nCurSum = nGreatestSum = 0;

       for (unsigned int i=0; i < nLength;++i)

       {

              nCurSum += pData[i];

              //if the current sum is negativediscard it

              if (nCurSum < 0)

                     nCurSum = 0;

              //if a greater sum is found,update the greatest sum

              if(nCurSum > nGreatestSum)

                     nGreatestSum = nCurSum;

}

//if all data are negative, find thegreatest element in the array

if (nGreatestSum == 0)

{

       nGreatestSum= pData[0];

       for(unsignedint i=1; i<nLength; ++i)

{

       if(pData[i]> nGreatestSum)

              nGreatestSum= pData[i];

}

}

return true;

}

函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志，如果函数返回值的是子数组和的最大值，那么当输入一个空指针应该返回何值？如果返回0，那这个函数的用户怎么区分输入无效和子数组的最大值刚好是0这两种情况？基于上述考虑，应该把子数组和的最大值以引用的方式放到参数列表中，同时让函数返回一个函数是否正常执行的标志。

输入有一类特殊情况需要特殊处理，当输入数组中所有整数都是负数时，子数组和的最大值就是数组中最大元素。

【Data Structure & Algorithm】求子数组的最大和的相关教程结束。