問題描述

給定由n個整數（包含負整數）組成的序列a1,a2,…,an，求該序列子段和的最大值。規定當所有整數均為負值時定義其最大子段和為0

窮舉法

最簡單的方法就是窮舉法，用一個變量指示求和的開始位置，一個變量指示結束位置，再一個變量指示當前要加和的位置，每一個開始位置對應n-i個結束位置，遍歷一遍就能得到最大值

int maxSubArray(int a[], int n) {int maxsum = 0;for (int i = 0; i < n; i++) {//開始位置for (int j = i; j < n; j++) {//結束位置int nowsum = 0;for (int k = i; k <= j; k++) {nowsum += a[k];if (nowsum > maxsum)maxsum = nowsum;}}}return maxsum;
}

算法有三重循環，時間復雜性為O(n^3)

窮舉法優化
當字段的開始下標確定后，要計算[i:j]的字段和可以利用上一次計算的[i:j-1]的字段和，加上a[j]就可以了

int maxSubArray2(int a[], int n) {int maxsum = 0;for (int i = 0; i < n; i++) {//開始位置int nowsum = 0;for (int j = i; j < n; j++) {//結束位置nowsum += a[j];if (nowsum > maxsum)maxsum = nowsum;}}return maxsum;
}

改進后的時間復雜度為O(n^2)

分治法

該問題也可以用分治法解決

分治策略思想如下:
將所給序列a[1:n]分成長度相同的兩端a[1:n/2]、a[n/2 +1:n]，分別求出這兩段的最大子段和，則整體序列a[1:n]的最大子段和有以下三種情況

• a[1:n]的最大子段和與a[1:n/2]的最大子段和相同
• a[1:n]的最大子段和與a[n/2 +1:n]的最大子段和相同
• a[1:n]的最大子段和是a[1:n/2]最后一段加a[n/2 +1:n]最開始一段的和

前兩種情況可以遞歸求得。對于第三種情況，可以發現，a[n/2]和a[n/2 +1]都在最大子段里，我們可以從a[n/2]向左、從a[n/2 +1]向右分別計算兩個最大字段和s1和s2，s1+s2就是最大子段和

遞歸方程

$$\text{MaxSum}(low,high)=?\begin{array}{ll}\max \left(0,\text{arr}[low]\right)& \text{if?}low=high\\ \max ?\begin{array}{l}\text{MaxSum}(low,mid)\\ \text{MaxSum}(mid+1,high)\\ \text{CrossSum}(low,mid,high)\end{array}& \text{otherwise}\end{array}$$

代碼

int maxSubArray3(int a[], int left, int right) {if (left == right)return a[left];int mid = (left + right) / 2;int maxleft = maxSubArray3(a, left, mid);int maxright = maxSubArray3(a, mid + 1, right);int maxleftsum = 0, maxrightsum = 0;int nowsum = 0;for (int i = mid; i >= left; i--) {nowsum += a[i];if (nowsum > maxleftsum)maxleftsum = nowsum;}nowsum = 0;for (int i = mid + 1; i <= right; i++) {nowsum += a[i];if (nowsum > maxrightsum)maxrightsum = nowsum;}return max(maxleft, max(maxright, maxleftsum + maxrightsum));
}

$$T(n)={\{}_{2T(\frac{n}{2})+O(n)n>c}^{O(1)n\le c}$$
根據master定理，我們得到
$T(n)=O(nlog)$

比起窮舉法的O(n^2)更優了

動態規劃

設數組為 a[1..n]，定義狀態 b[i] 表示以 a[i] 結尾的子段的最大和，則最大字段和為$max{b}_j$

有遞歸方程：
$$b[i]=\{\begin{array}{ll}0& i=0(\text{邊界條件})\\ \max (b[i?1]+a[i],a[i])& i\ge 1\end{array}$$
全局最大子段和為所有 b[i] 中的最大值，并與0比較：
$$\text{MaxSum}=\max \left(0,\underset{1\le i\le n}{\max }b[i]\right)$$

計算最優值

使用變量b記錄此前最大字段和，如果為負數則當前最大和為a[i]，如果為正數則最大和為b+a[i]
代碼

int maxSubArray4(int a[], int n) {int b = 0;int maxsum = 0;for (int i = 0; i < n; i++) {if (b > 0)b += a[i];else b = a[i];if (b > maxsum)maxsum = b;}return maxsum;
}

構造最優解

使用兩個變量start和end記錄最大字段的起始和結束位置

int maxSubArray4(int a[], int n, int* start, int* end) {int b = 0;int max_sum = 0;int current_start = 0;  // 當前子段起始位置*start = *end = -1;     // 默認無效索引for (int i = 0; i < n; i++) {if (b > 0) {b += a[i];}else {b = a[i];current_start = i;  // 重置起點}// 更新全局最大值及索引if (b > max_sum) {max_sum = b;*start = current_start;*end = i;}}// 處理全負數情況：返回0且不記錄索引if (max_sum <= 0) {*start = *end = -1;return 0;}return max_sum;
}

時間負責度：O(n)

實例

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//窮舉法
int maxSubArray(int a[], int n) {int maxsum = 0;for (int i = 0; i < n; i++) {//開始位置for (int j = i; j < n; j++) {//結束位置int nowsum = 0;for (int k = i; k <= j; k++) {nowsum += a[k];if (nowsum > maxsum)maxsum = nowsum;}}}return maxsum;
}
//窮舉法優化
int maxSubArray2(int a[], int n) {int maxsum = 0;for (int i = 0; i < n; i++) {//開始位置int nowsum = 0;for (int j = i; j < n; j++) {//結束位置nowsum += a[j];if (nowsum > maxsum)maxsum = nowsum;}}return maxsum;
}
//分治法
int maxSubArray3(int a[], int left, int right) {if (left == right)return a[left];int mid = (left + right) / 2;int maxleft = maxSubArray3(a, left, mid);int maxright = maxSubArray3(a, mid + 1, right);int maxleftsum = 0, maxrightsum = 0;int nowsum = 0;for (int i = mid; i >= left; i--) {nowsum += a[i];if (nowsum > maxleftsum)maxleftsum = nowsum;}nowsum = 0;for (int i = mid + 1; i <= right; i++) {nowsum += a[i];if (nowsum > maxrightsum) {maxrightsum = nowsum;}}return max(maxleft, max(maxright, maxleftsum + maxrightsum));
}
//動態規劃
int maxSubArray4(int a[], int n, int* start, int* end) {int b = 0;int max_sum = 0;int current_start = 0;  // 當前子段起始位置*start = *end = -1;     // 默認無效索引for (int i = 0; i < n; i++) {if (b > 0) {b += a[i];}else {b = a[i];current_start = i;  // 重置起點}// 更新全局最大值及索引if (b > max_sum) {max_sum = b;*start = current_start;*end = i;}}// 處理全負數情況：返回0且不記錄索引if (max_sum <= 0) {*start = *end = -1;return 0;}return max_sum;
}
int main() {int a[] = { 1, -2, 3, 10, -4, 7, 2, -5 };cout << maxSubArray(a, 8) << endl;cout << maxSubArray2(a, 8) << endl;cout << maxSubArray3(a, 0, 7) << endl;int start, end;cout << maxSubArray4(a, 8, &start, &end) << endl;cout <<"start:" << start << " " <<"end:"<< end << endl;return 0;
}

運行結果