![]()
2.5 最?連續(xù)?數組和 ????
題目描述:
給定?個整數數組，數組?可能有正數、負數和零。數組中連續(xù)的?個或多個整數組成?個?數組，每個?數組都有?個和。求所有?數組的和的最?值。例如，如果輸?的數組為{1, ?2, 3, 10, ?4,
7, 2, ?5}，和最?的?數組為{3, 10, ?4, 7, 2}，那么輸出為該?數組的和18。
題?解析:
解法?：蠻?枚舉 ????
要求解一個數組的最大連續(xù)子數組和，最直觀、最野蠻的方法是使用三個for循環(huán)三層遍歷，求出數組中每一個子數組的和，最終找出這些子數組和中的最大值。令 currSum[i,…,??j] 為數組 A 中第 i 個元素到第 j 個元素的和（其中 0≤i≤j maxSum) {
????????maxSum = currSum;
??????}
??????// 這里要記得清零，否則 sum 最終存放的是所有子數組的和
??????currSum = 0;
????}
??}
??return maxSum;
}
```
這種方法的時間復雜度為 O(n^3)。?
解法?：動態(tài)規(guī)劃 ????
事實上，我們可以令 currSum 表示以當前元素結尾的最大連續(xù)子數組的和，maxSum 表示全局的最大子數組的和。當往后掃描時，對第 j 個元素有兩種選擇，要么放入前面找到的子數組，要么作為新子數組的第一個元素。如果 currSum > 0，則令 currSum 加上 A[j]；如果 currSum < 0，則 currSum 被置為當前元素，即 currSum = A[j]。這相當于是說，如果設 currSum(j) 為以 j 結尾的最大連續(xù)子數組的和，那么 currSum(j) = max{0, currSum[j?1]} + A[j]。如果 maxSum < currSum，則更新 maxSum = currSum；否則 maxSum 保持原值，不更新。舉個例子，如果輸入數組是 {1, ?2, 3, 10, ?4, 7, 2, ?5}，那么 currSum 和 maxSum 的變化分別為：
currSum：0→1→-1→3→13→9→16→18→13；
maxSum：0→1→1→3→13→13→16→18→18
參考代碼如下：
```c
int MaxSubArray(int* A, int n) {
??int currSum = 0;
??int maxSum = A[0]; // 數組元素全為負的情況，返回最大數
??for (int j = 0; j < n; j++) {
????if (currSum >= 0) {
??????currSum += A[j];
????} else {
??????currSum = A[j];
????}
????if (currSum > maxSum) {
??????maxSum = currSum;
????}
??}
??return maxSum;
}
```
這個方法從前往后掃描一遍數組，即可求得最大連續(xù)子數組和，時間復雜度為 O(n)。 ????
希望這些解法能幫助你更專業(yè)地理解并解決這個問題！如果有任何疑問或需要進一步的解釋，請隨時提出。 ???????
標簽：
