同樣：部落格的主要目的在于記錄求解時的思路。
題目：給定一個整數數組，請找出一個連續子數組，使得該子數組的和最大。輸出答案時，請分别傳回第一個數字和最後一個數字的下标。（如果兩個相同的答案，請傳回其中任意一個）
方法1：窮舉法，計算出任意一個數的所有子數組的和，并找出最大的，同時記錄起始和結束index.
下面根據樣例來說明， 給定 [-3, 1, 3, -3, 4]，根據窮舉法可以得到如下的表格：
第i行j列（j > i ) 表示 數組中i ~j之間數的和。通過表格可以直接找到最大的子數組和并确定起始位置（圖中的第二列第五行，對應數組中[1,4]）。
該方案代碼如下：
class Solution {
public:
/*
* @param A: An integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> continuousSubarraySum(vector<int> &A) {
// write your code here
// solution 1
int maxSum = -;
int indexStart = ;
int indexEnd = ;
for ( int i = ; i < A.size(); i++ )
{
int j = i;
int tmpSum = ;
for ( ; j < A.size(); j++ )
{
tmpSum += A[j];
if ( tmpSum > maxSum )
{
maxSum = tmpSum;
indexStart = i;
indexEnd = j;
}
}
}
vector<int> vecRet;
vecRet.push_back(indexStart);
vecRet.push_back(indexEnd);
return vecRet;
}
};
時間複雜度 T = n + (n-1) + …1 ⇒ O(N^2) ；空間複雜度 O(1)。
該代碼在lintCode上運作之後，會發生逾時現象，原因就在于時間複雜度太高。那麼可以用什麼方案進行優化呢。通過觀察上面的表格，很容易發現後面的資料被加了很多次，另外可以看到，每一列最後一個數等于當列第一個數和下一列的最後一個數的和，即以i開始子數組和Sum(i)等于 A[i] + Sum(i+1) ==> Sum(i) = A[i] + Sum(i+1)。
那麼，要使Sum(i) 最大該如何做呢，其實就很簡單了。
SumMax(i) = A[i] + Sum(i+1) > 0 ? Sum(i+1) : 0;
從動态規劃裡看，這應該屬于此問題的最優子結構了，邊界就是 Sum(A.size() -1) = A[A.size()-1]了。計算出每一個數開始的最大子數組和，然後找出最大的就可以得到結果了。根據邊界來看，顯然從後往前計算，時間上更優，還是上面的例子，從後往前計算，可以得到如下的最大字數和的數組。
箭頭表示計算方向，找到最大的數所在的index,即為起始index，往後直到子數組和小于0為止，即為終止index.
代碼如下：
class Solution {
public:
/*
* @param A: An integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> continuousSubarraySum(vector<int> &A) {
// write your code here
// solution 2
vector<int> partSum;
partSum.resize(A.size(), );
int nLen = A.size();
int maxSum = -;
int indexStart = ;
int indexEnd = nLen - ;
int indexTmp = nLen - ;
for ( int j = nLen - ; j >= ; j-- )
{
if ( j == nLen - )
{
partSum[j] = A[j];
if ( partSum[j] > maxSum )
{
indexStart = j;
maxSum = partSum[j];
}
continue;
}
if ( partSum[j+] >= )
{
partSum[j] = partSum[j+] + A[j];
}
else
{
partSum[j] = A[j];
indexTmp = j; //重置臨時的終點位置
}
if ( partSum[j] > maxSum )
{
indexStart = j;
maxSum = partSum[j];
indexEnd = indexTmp; // 臨時終點位置生效
}
}
vector<int> ret;
ret.push_back(indexStart);
ret.push_back(indexEnd);
return ret;
}
};
上述方案，僅需周遊一遍數組即可求得最大的連續子數組和。時間複雜度O(N)，空間複雜度O(N)。但也很容易的看出，空間複雜度可以降為O(1)。
總結：此題的關鍵在于找出子數組和與數組之間的關系。很多時候一眼想不出最佳的方案時，不妨先把暴力解法寫出來，然後看看是否能優化。