UVa 836 Largest Submatrix

想法：
    這題是2維MSS(minimum subarray sum)，基本上第一個for loop先選出submatrix的垂直邊長，第二個for loop選定這條邊起始位置，然後向右做MMS。

	#include <iostream>
	#include <string>
	using namespace std;
	string Matrix[1000];
	bool is1(int i, int i_end, int j);
	int main()
	{
	ios::sync_with_stdio(false);
	int Case;
	cin >> Case;
	while (Case--)
	{
	cin >> Matrix[0];
	int N = Matrix[0].size();
	for (int i = 1; i < N; ++i)
	cin >> Matrix[i];
	int MSS = 0, Max = 0;
	for (int Len = 1; Len <= N; ++Len) {
	for (int i = 0; i + Len - 1 < N; ++i) {
	MSS = 0;
	for (int j = 0; j < N; ++j) {
	if (is1(i, i+Len-1, j))
	MSS += Len;
	else
	MSS = 0;
	if (MSS > Max) Max = MSS;
	}
	}
	}
	cout << Max << endl;
	if (Case) cout << endl;
	}
	}
	bool is1(int i, int i_end, int j)
	{
	for (i; i <= i_end; ++i)
	if (Matrix[i][j] != '1')
	return false;
	return true;
	}

view raw [UVa] 836 Largest Submatrix.cpp hosted with ❤ by GitHub