d206 - 00108 - Maximum Sum

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出一個 N x N 陣列中，和最大的子矩陣的和。子矩陣必須是相連的，大小可以任意。

解題思路

本題可以使用 Kadane's Algorithm 的變形來解決。首先，計算每一列的前綴和，將二維問題轉化為一維問題。然後，對於每一對列 (left, right)，計算從 left 到 right 的列的和，並使用 Kadane's Algorithm 找出最大子陣列的和。最後，更新全局最大值。

具體來說，t[i][j+1] 儲存 a[i][0] 到 a[i][j] 的和。對於每一對列 k 和 j，計算從第 k 列到第 j 列的和，然後使用 Kadane's Algorithm 找出最大子陣列的和。Kadane's Algorithm 的核心思想是，維護一個當前最大和 tmp 和一個全局最大和 ans。對於每一行 i，計算 t[i][j] - t[i][k]，表示從第 k 列到第 j 列的和。然後，更新 tmp 和 ans。

複雜度分析

• 時間複雜度: O(n^3)
• 空間複雜度: O(n^2)

程式碼

#include <iostream>
using namespace std;
int a[101][101],n,t[102][102];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j){
				cin >> a[i][j];
				t[i][j+1]=a[i][j]+t[i][j];
			}
		}
		int ans=0;
		for(int k=0;k<=n;++k){
			for(int j=k+1;j<=n;++j){
				int tmp=0;
				for(int i=0;i<n;++i){
					tmp=max(t[i][j]-t[i][k],t[i][j]-t[i][k]+tmp);
					ans=max(tmp,ans);
				}
			}
		}
		cout << ans << "\n";
	}
}