題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。

例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。

分析：本題最初為2005年浙江大學(xué)計(jì)算機(jī)系的考研題的最后一道程序設(shè)計(jì)題，在2006年里包括google在內(nèi)的很多知名公司都把本題當(dāng)作面試題。由于本題在網(wǎng)絡(luò)中廣為流傳，本題也順利成為2006年程序員面試題中經(jīng)典中的經(jīng)典。

如果不考慮時(shí)間復(fù)雜度，我們可以枚舉出所有子數(shù)組并求出他們的和。不過非常遺憾的是，由于長(zhǎng)度為n的數(shù)組有O(n²)個(gè)子數(shù)組；而且求一個(gè)長(zhǎng)度為n的數(shù)組的和的時(shí)間復(fù)雜度為O(n)。因此這種思路的時(shí)間是O(n³)。

很容易理解，當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)負(fù)數(shù)將會(huì)減少接下來的和。基于這樣的思路，我們可以寫出如下代碼。

參考代碼：

/ // 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 arrayunsigned int nLength, // the length of arrayint &nGreatestSum // the greatest sum of all sub-arrays ) {// if the input is invalid, return falseif((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 itif(nCurSum < 0)nCurSum = 0;// if a greater sum is found, update the greatest sumif(nCurSum > nGreatestSum)nGreatestSum = nCurSum;}// if all data are negative, find the greatest element in the arrayif(nGreatestSum == 0){nGreatestSum = pData[0];for(unsigned int i = 1; i < nLength; ++i){if(pData[i] > nGreatestSum)nGreatestSum = pData[i];}}return true; }

討論：上述代碼中有兩點(diǎn)值得和大家討論一下：

·???????? 函數(shù)的返回值不是子數(shù)組和的最大值，而是一個(gè)判斷輸入是否有效的標(biāo)志。如果函數(shù)返回值的是子數(shù)組和的最大值，那么當(dāng)輸入一個(gè)空指針是應(yīng)該返回什么呢？返回0？那這個(gè)函數(shù)的用戶怎么區(qū)分輸入無效和子數(shù)組和的最大值剛好是0這兩中情況呢？基于這個(gè)考慮，本人認(rèn)為把子數(shù)組和的最大值以引用的方式放到參數(shù)列表中，同時(shí)讓函數(shù)返回一個(gè)函數(shù)是否正常執(zhí)行的標(biāo)志。

·???????? 輸入有一類特殊情況需要特殊處理。當(dāng)輸入數(shù)組中所有整數(shù)都是負(fù)數(shù)時(shí)，子數(shù)組和的最大值就是數(shù)組中的最大元素。

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動(dòng)，書中的分析講解更加詳細(xì)，討論了這種方法和動(dòng)態(tài)規(guī)劃方法的聯(lián)系。歡迎關(guān)注。在我的英文博客里也有這道題的講解，

感興趣的讀者可以參考 http://codercareer.blogspot.com/2011/09/no-03-maximum-sum-of-all-sub-arrays.html。
??????????? 本題已被 九度Online Judge系統(tǒng)收錄，歡迎讀者移步到 http://ac.jobdu.com/hhtproblems.php在線測(cè)試自己的代碼。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。對(duì)解題思路有任何建議，歡迎在評(píng)論中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht與我討論。謝謝。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(03)－子数组的最大和[算法]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。