《劍指offer》面試題31：

題目： 輸入一個整型數組，數組里有正數也有負數。數組中一個或連續的多個整數組成的一個子數組，求所有子數組的和的最大值，要求時間復雜度為O(n)。

分析：一個變量保存目前的子數組的和，一個變量保存目前最大的子數組的和。當遍歷到某一個值時，如果第一個變量值變為負數，則將其舍掉，繼續往下遍歷；如果當前子數組的和大于保存的最大子數組的和，將當前子數組的和賦值給第二個變量。這樣復雜度為O(n)。

代碼：

注釋掉的為《劍指offer》中的代碼，其中最大子數組的和初始化為0x8000 0000，int型的最小范圍是-2^31~2^31,0x8000 0000是int型表示最小范圍時的負數最小值，感覺這樣初始化不好，未注釋的是自己寫的代碼。

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];elsenCurSum += pData[i];if(nCurSum > nGreatestSum)nGreatestSum = nCurSum;}*///修改int nCurSum = pData[0];int nGreatestSum = pData[0];for( int i = 1; i < nLength; ++i ){nCurSum += pData[i];if( nCurSum < 0 ){nCurSum = 0;}else if(nCurSum > nGreatestSum){nGreatestSum = nCurSum;}}return nGreatestSum; }

總結

以上是生活随笔為你收集整理的面试题整理9 连续子数组的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。