# 題目: UVa 11951 - Area

# 題目說明

有一個N * M大小的矩陣，求子矩陣合 <= K的最大子矩陣範圍

---

INPUT:
第一行輸入一個整數T，代表測資數
每筆測資第一行有三個整數N、M、K
接下來有N * M個整數，代表矩陣的值

---

OUTPUT:
輸出子矩陣合 <= K的最大子矩陣範圍

# 解題方法

先建表儲存矩陣的值

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

以一個變數top控制起點，若目前localmax > K則將範圍下移一格
計算目前的範圍及子矩陣合，最後儲存最大的範圍至maxS、最小的值至maxP

# 參考程式

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

using namespace std;

int T, N, M, K;
int l, r, maxS, maxP;
int G[101][101];
int sum[101];

// Kadane's Algorithm
void max1d()
{
	int top = 0, localsum = 0;

	for (int i = 0; i < N; ++i)
	{
		localsum += sum[i];
		while (localsum > K) localsum -= sum[top++];

		int localS = (r - l + 1) * (i - top + 1);
		if (localS > maxS) maxS = localS, maxP = localsum;
		else if (localS == maxS) maxP = min(maxP, localsum);
	}
}

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

	cin >> T;

	for (int cases = 1; cases <= T; ++cases)
	{
		cin >> N >> M >> K;
		// init
		memset(G, 0, sizeof(G));
		maxS = 0;
		maxP = INT_MAX;

		// store data in graph
		for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> G[i][j];

		for (l = 0; l < M; ++l)
		{
			memset(sum, 0, sizeof(sum));

			for (r = l; r < M; ++r)
			{
				for (int i = 0; i < N; ++i) sum[i] += G[i][r];
				max1d();
			}
		}

		cout << "Case #" << cases << ": " << maxS << " " << maxP << "\n";
	}

	return 0;
}

# 參考資料

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