問題：
1. 一個由N個整數元素的一維數組，求其所有子數組中元素和的最大值。
2. 如果數組首尾相鄰，也就是允許子數組A[i],...,A[n-1],A[0],...,A[j]存在，求其所有子數組總元素和的最大值。
1. 解法：
我們使用動態規劃的思想可以在O(n)的時間內計算出子數組之和最大值。
動態規劃問題往往非常靈活，所以在做題的時候不知道如何編寫，其實它有很清晰的分析方法，按照這個方法就可以較容易的解決動態規劃的問題。具體參考IOI2000 張辰的論文《動態規劃的特點及其應用》
階段：在所有以元素k結尾的子數組中，選出元素和最大的子數組，k=1,2...n。
狀態：以元素k結尾的和最大的子數組是包含以元素k-1結尾的和最大的子數組還是就只有元素k這一個元素，即有這兩個可選狀態。
之所以選擇這樣的階段和狀態，因為這種選擇方式具有無後效性，即階段k+1（以元素k+1結尾的子數組）只會與階段k（以元素k結尾的子數組）發生關聯，而與其它階段無關。在得到以每個元素結尾的和最大的子數組之後，只要取其中最大值就是所有子數組中最大的子數組。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN];
// 動態規劃思想，時間復雜度O(n)
int Tail[MAXN];
int main()
{
int n, i, j, k;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
// 計算以k結尾的子數組之和的最大值，即子數組包含第k個數
Tail[1] = A[1];
for (k=2; k<=n; k++) // k個階段
Tail[k] = max(A[k],Tail[k-1]+A[k]); // 只有兩個狀態
// 因為和最大的子數組肯定以某個數結尾，所以取這n個子數組的最大值
// 就是和最大的子數組
int All = Tail[1];
for (i=2; i<=n; i++)
All = max(All, Tail[i]);
cout << All;
}
雖然這種標准的動態規劃方法時間復雜度已經最優了，但它仍要占用O(n)的空間，對於一般的動態規劃問題占用較多的空間是不可避免的，但這個問題較簡單，仍可以繼續優化。我們把All取最大值的操作放入Tail的計算循環中，如下：
Tail[1] = A[1];
All = Tail[1];
for (k=2; k<=n; k++)// k個階段
{
Tail[k] = max(A[k],Tail[k-1]+A[k]);// 只有兩個狀態
All = max(All, Tail[k]);
}
由於循環體中只關心當前的Tail[k]和上一個Tail[k-1]，可以省去之前所計算出的Tail[1],Tail[2]...Tail[k-2]的數據，如下：
Tail = A[1];
All = Tail;
for (k=2; k<=n; k++)// k個階段
{
Tail = max(A[k],Tail+A[k]);// 只有兩個狀態
All = max(All, Tail);
}
最後優化後的代碼就是書中最後給出的結果。
2. 解法：
把問題分為兩種情況：
(1)最大和子數組沒有跨過A[n]到A[1]（如問題1）
(2)最大和子數組跨過A[n]到A[1]
對於情況(2)，這樣的最大和子數組包含兩個部分：以A[1]開始的最大和子數組，以及以A[n]結尾的最大和子數組，並且這兩個子數組不允許重疊，那麼將這兩個子數組拼合起來就是情況(2)的解。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN];
int main()
{
int n, i, j, k;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
// 和最大的子數組沒有跨過A[n]和A[1]
int Tail = A[1];
int All = Tail;
for (k=2; k<=n; k++) // k個階段
{
Tail = max(A[k],Tail+A[k]); // 只有兩個狀態
All = max(All, Tail);
}
// 和最大的子數組跨過了A[n]和A[1]
int Start = A[1];
for (i=2; i<=n && Start+A[i]>Start; i++)
Start += A[i];
Tail = A[n];
for (j=n-1; j>=1 && Tail+A[j]>Tail; j--)
Tail += A[j];
if (i<j && Start+Tail > All)
All = Start+Tail;
cout << All;
}
作者：linyunzju
