# 題目: UVa 10827 - Maximum sum on a torus

# 題目說明

求一個N * N大小矩陣的最大子矩陣合，子矩陣可跨越邊線組合

---

INPUT:
第一行輸入一個整數T，代表測資數
每筆測資第一行有一個整數N，代表陣列的大小
接下來會有N * N個整數，代表矩陣的值

---

OUTPUT:
輸出最大的子矩陣合

# 解題方法

先建表儲存矩陣的值

將2D最大子矩陣合透過2層迴圈壓縮成1D最大子矩陣合的問題

1. 利用一個變數st解決左右超出的問題
2. 上下超出的問題可視為整個矩陣 - 最小子矩陣

# 參考程式碼

#include <iostream>
#include <memory.h>

using namespace std;

int N;
int G[152][76];
int sum[76];

// Kadane's Algorithm
int max1d()
{
	int globalmax, localmax, globalmin, localmin, total;
	globalmax = localmax = globalmin = localmin = total = sum[0];

	for (int i = 1; i < N; ++i)
	{
		total += sum[i];

		localmax = max(localmax + sum[i], sum[i]);
		localmin = min(localmin + sum[i], sum[i]);

		globalmax = max(globalmax, localmax);
		globalmin = min(globalmin, localmin);
	}

	return max(globalmax, total - globalmin);
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int T;
	cin >> T;

	while (T-- && cin >> N)
	{
		memset(G, 0, sizeof(G));
		int Max = -100;

		// store data in graph
		for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> G[i][j];
		
		for (int i = 0; i < N; ++i)
		{
			memset(sum, 0, sizeof(sum));

			for (int j = 0, st = i; j < N; ++j, ++st)
			{
				if (st == N) st = 0;
				for (int k = 0; k < N; ++k) sum[k] += G[k][st];
				Max = max(Max, max1d());
			}
		}

		cout << Max << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa-10827/