程序員面試題精選(03)－求子數組的最大和
分類(lèi)：
技術(shù) | 標簽：
編程,
就業(yè),
找工作題目：輸入一個(gè)整形數組，數組里有正數也有復數。數組中連續的一個(gè)或多個(gè)整數組成一個(gè)子數組，每個(gè)子數組都有一個(gè)和。求所有子數組的和的最大值。要求時(shí)間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，因此輸出為該子數組的和18。
分析：本題最初為2005年浙江大學(xué)計算機系的考研題的最后一道程序設計題，在2006年里包括google在內的很多知名公司都把本題當作面試題。由于本題在網(wǎng)絡(luò )中廣為流傳，本題也順利成為2006年程序員面試題中經(jīng)典中的經(jīng)典。
如果不考慮時(shí)間復雜度，我們可以枚舉出所有子數組并求出他們的和。不過(guò)非常遺憾的是，由于長(cháng)度為n的數組有O(n2)個(gè)子數組；而且求一個(gè)長(cháng)度為n的數組的和的時(shí)間復雜度為O(n)。因此這種思路的時(shí)間是O(n3)。
很容易理解，當我們加上一個(gè)正數時(shí)，和會(huì )增加；當我們加上一個(gè)負數時(shí)，和會(huì )減少。如果當前得到的和是個(gè)負數，那么這個(gè)和在接下來(lái)的累加中應該拋棄并重新清零，不然的話(huà)這個(gè)負數將會(huì )減少接下來(lái)的和?；谶@樣的思路，我們可以寫(xiě)出如下代碼。
參考代碼：
/////////////////////////////////////////////////////////////////////////////
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool FindGreatestSumOfSubArray
(
int *pData, // an array
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
)
{
// if the input is invalid, return false
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 negative, discard 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 the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
nGreatestSum = pData[i];
}
}
return true;
}
討論：上述代碼中有兩點(diǎn)值得和大家討論一下：
· 函數的返回值不是子數組和的最大值，而是一個(gè)判斷輸入是否有效的標志。如果函數返回值的是子數組和的最大值，那么當輸入一個(gè)空指針是應該返回什么呢？返回0？那這個(gè)函數的用戶(hù)怎么區分輸入無(wú)效和子數組和的最大值剛好是0這兩中情況呢？基于這個(gè)考慮，本人認為把子數組和的最大值以引用的方式放到參數列表中，同時(shí)讓函數返回一個(gè)函數是否正常執行的標志。
· 輸入有一類(lèi)特殊情況需要特殊處理。當輸入數組中所有整數都是負數時(shí)，子數組和的最大值就是數組中的最大元素。
