# 演算法課程題解 - 動態規劃\: 最大連續和

# UVa 10684
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10684

在一個賭場當中有個人在研究賭客的輸贏情形
已知每個賭局最大可以贏得多少錢，以正數與負數表示表示贏錢與輸錢
請問在連續的賭局當中最多可以贏得多少錢

## 想法 By Koios
題目的意思等價於求一個序列中子序列的最大連續和
那麼每個數字有兩種情況，一種是被包含在一個已存在的連續序列當中; 另一種是它是新的連續子序列的開頭

定義 $dp[i][j]$ 表示第 $i$ 項在兩種情況當中前 $i$ 項的最大連續和
其中 $j=0$ 表示第 $i$ 項包含在已存在的連續序列當中
而 $j=1$ 表示第 $i$ 項維新的連續序列的開頭

則有轉移式
$$
\begin{cases}
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + arr[i] \\
dp[i][1] = arr[i]
\end{cases}
$$

並且
$$
\begin{cases}
dp[0][0] = 0 \\
dp[0][1] = arr[0]
\end{cases}
$$

可以發現到每項 $dp$ 值都只跟前一項有關，並且每次每項 $dp$ 值都會完全被覆蓋，所以可以使用模運算優化記憶體使用量
同時，每項 $arr$ 都只會使用一次，所以不需要陣列，可以改用一個變數取代，在輸入同時計算 $dp$ 值

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int n, ans, m, dp[2][2];

int main(){
	while(cin>>n && n){
		ans = 0;
		dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
		for(int i=0 ; i<n ; i++){
			cin>>m;
			if(i == 0) dp[0][1] = m;
			else{
				dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1]) + m;
				dp[i%2][1] = m;
			}
			ans = max(ans, max(dp[i%2][0], dp[i%2][1]));
		}
		if(ans == 0){
			cout<<"Losing streak.\n";
		}
		else{
			cout<<"The maximum winning streak is "<<ans<<".\n";
		}
	}
	return 0;
}

### 時間複雜度分析
每筆測資時間複雜度為 $O(n)$

# UVa 108
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?108

給一個 $n \times n$ 的序列，請找出最大子區域和
一個子區域是在 $n \times n$ 序列中任意大小的矩形
子區域合的定義為該區域內所有元素的和

## 想法 By Koios
如果我們現在**只看其中一列**，我們會怎麼計算它的最大總和呢?
對於每個數字都有兩種選擇
1. 跟前面的數字組合
2. 自己作為新組合的開頭

定義 $dp[i]$ 表示前 $i$ 行的最大區間和
則有轉移式
$$
dp[i] = max(dp[i], dp[i-1] + arr[i])
$$

並且 $dp$ 的初始值是序列中的第一個元素
不過如果說第一個元素就已經小於零了，那麼不取它必定會拿到更好的解
$$
dp[0] = max(0, arr[i])
$$

看完如何計算一行的最大區間和之後，接下來看二維

---

如果給定一個 $n \times n$ 的矩形區域，要求寬度同樣是 $n$ 的最大子區域和要怎麼求呢? 也就是說現在矩形的**寬是固定的，只有高變動**
因為寬是固定的，那麼當我們選擇某一列，那一列的全部元素都必須要被加起來
所以每一列**只需要考慮加總後的結果**
最終，我們可以把這個問題轉化成前面提到的一維最大區間和!

現在 $arr[i]$ 表示的是第 $i$ 列的總和
定義 $dp[i]$ 表示前 $i$ 列的最大區間和
則有轉移式
$$
dp[i] = max(dp[i], dp[i-1] + arr[i])
$$

同樣的
$$
dp[0] = max(0, arr[0])
$$

---

接下來把寬也考慮進來
我們現在已經可以做到**固定寬的矩形最大子區域和**
那麼，我們可以考慮直接枚舉左界以及右界，這樣就可以得到所有子區域的最大和了!

尋找固定寬的矩形最大子區域和所需的時間複雜度為 O(n)
枚舉左界以及右界時間複雜度為 O(n^2)
這樣做的總時間複雜度為 O(n^3)，在可以接受的範圍內

前面的 $arr[i]$ 表示的是第 $i$ 列區間 $[L, R]$ 的總和
如果每次重算就還需要花一個 $O(n)$
這裡可以用前綴和先優化

定義 $arr[i][j]$ 表示原矩形的陣列
定義 $cnt[i][j]$ 表示第 $i$ 列前 $j$ 行的元素總和
$$
\begin{cases}
cnt[i][j] = arr[i][j] \quad \texttt{ if }j=0 \\
cnt[i][j] = cnt[i][j-1] + arr[i][j] \quad \texttt{else}
\end{cases}
$$
那麼要得到第 $i$ 列的區間 $[L, R]$ 總和就可以用 $cnt[i][R] - cnt[i][L-1]$ 取得

定義 $dp[i]$ 表示在固定矩形寬度在區間 $[L, R]$ 的情況下，前 $i$ 列最大區間和
$$
dp[i] = max(dp[i], dp[i-1] + (cnt[i][R]-cnt[i][L-1]))
$$
$$
dp[0] = max(0, (cnt[i][R]-cnt[i][L-1]))
$$

針對每個 $L, R$ 都找出一個區間最大和，其中的最大值就是本題答案

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int n, arr[105][105], cnt[105][105], dp[105];
int main(){
	cin>>n;
	for(int i=1 ; i<=n ; i++){
		for(int j=1 ; j<=n ; j++){
			cin>>arr[i][j];
			// 先計算出前綴和
			cnt[i][j] = cnt[i][j-1] + arr[i][j];
		}
	}
	int ans = 0;
	for(int L=1 ; L<=n ; L++){
		int cur=0;
		for(int R=L ; R<=n ; R++){
			// 這邊固定好長寬了，可以用一維 dp 找到區間最大矩形和
			dp[0] = max(0, cnt[0][R]-cnt[0][L-1]);
			for(int i=1 ; i<=n ; i++){
				int sum = cnt[i][R]-cnt[i][L-1];
				dp[i] = max(sum, dp[i-1] + sum);
				cur = max(cur, dp[i]);
			}
			ans = max(ans, cur);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

### 時間複雜度分析
輸入以及初始化前綴和時間複雜度為 $O(n^2)$
DP 每種狀態轉移時間複雜度維 $O(1)$，總共有 $n$ 種狀態，每次 DP 時間複雜度為 $O(n)$
DP 總共需要做 $n^2$ 次，總時間複雜度為 $O(n^3)$
總時間複雜度為 $O(n^3)$

# UVa 10755
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10755

跟 UVa 108 類似，不過這次進化成 3 維的問題
做法相同，我們會做 DP 的部分仍然是只有一維
我們要枚舉長方體的高、寬分別是從哪裡到哪裡

固定好長寬之後，就可以把在這個高度中的每個二維矩陣加起來，變成一個新的二維矩陣
二維矩陣加的方向可以參考下圖


接下來就又回到 UVa 108 的二維最大區間和了!
關於二維的做法可以參考 UVa 108 的題解

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
const long long MinN = -9223372036854775807;
int t, A, B, C;
bool out=false;
long long ans, arr[25][25][25], arr2[25][25], cnt[25][25], dp[25];

int main(){
	cin>>t;
	while(t--){
		if(out) cout<<"\n";
		else out = true;
		
		cin>>A>>B>>C;
		for(int i=1 ; i<=A ; i++){
			for(int j=1 ; j<=B ; j++){
				for(int k=1 ; k<=C ; k++){
					cin>>arr[i][j][k];
				}
			}
		}
		
		ans = MinN;
		for(int st=1 ; st<=A ; st++){
			// 清空 arr2
			for(int i=1 ; i<=B ; i++){
				for(int j=1 ; j<=C ; j++){
					arr2[i][j] = 0;
				}
			}

			for(int ed=st ; ed<=A ; ed++){
				// 固定高了
				// 計算新的二維陣列
				for(int i=1 ; i<=B ; i++){
					for(int j=1 ; j<=C ; j++){
						// 等同於輸入二維陣列的每個值
						arr2[i][j] += arr[ed][i][j];
						// 計算前綴和
						cnt[i][j] = cnt[i][j-1] + arr2[i][j];
					}
				}
				
				for(int L=1 ; L<=C ; L++){
					long long cur = MinN;
					for(int R=L ; R<=C ; R++){
						// 固定寬了
						// 這次不需要跟 0 取 max ，因為至少要取一個
						dp[0] = cnt[0][R] - cnt[0][L-1];
						for(int i=1 ; i<=B ; i++){
							long long sum = cnt[i][R] - cnt[i][L-1];
							dp[i] = max(sum, dp[i-1] + sum);
							cur = max(cur, dp[i]);
						}
						ans = max(ans, cur);
					}
				}
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

### 時間複雜度分析
輸入時間複雜度為 $O(ABC)$
DP 每種轉移時間複雜度為 $O(1)$，總共有 $B$ 種狀態
總共需要做 $A^2C^2$ 次 DP ，總時間複雜度為 $O(A^2BC^2)$
總時間複雜度為 $O(t(A^2BC^2))$

###### tags: `SCIST 演算法 題解`