CI 20.12 - 최대 서브 매트릭스 와 문제

N * N 의 행렬 을 지정 하여 최대 서브 행렬 과.
생각:
최대 부분 과 문 제 는 동적 계획 으로 O (n) 에서 해결 할 수 있 고 이 문 제 는 최대 부분 과 해법 을 통 해 풀 수 있다.우 리 는 i 행 에서 j 행 까지 의 하위 행렬 을 고려 하여 i ~ j 행 의 행렬 을 1 차원 배열 로 합 칠 수 있다. 즉, 각 열 에 대응 하 는 수 를 더 하면 이 1 차원 배열 의 최대 부분 과 원자 행렬 의 최대 합 이다.
우 리 는 2 차원 배열 p 로 행렬 의 부분 과 'p [i] [j] 를 저장 합 니 다. 왼쪽 상단 은 (1, 1) 이 고 (아래 표 시 는 1 부터) 오른쪽 하단 은 (i, j) 행렬 의 요소 의 합 입 니 다.만약 에 우리 가 i ~ j 행, k ~ m 열의 행렬 에서 요소 의 합 을 요구한다 면 우 리 는 다음 식 으로 계산 할 수 있 습 니 다.

sum = p[j][m] - p[j][k-1] - p[i-1][m] + p[i-1][k-1]

O (1) 의 시간 만 필요 하 다.
부분 과 p [i] [j] 어떻게 계산 할 까요?우 리 는 더 작은 부분 과 계산 을 통 해 그것 을 얻 을 수 있다.

p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j]

그 중에서 a [i] [j] 는 행렬 의 정수 이다.저 희 는 O (n2) 만 필요 합 니 다. ) 모든 부분 과
그래서 총 시간 은 O (n3) 입 니 다. )。

#include 
#include 
using namespace std;

const int N = 101;
int a[N][N], p[N][N];

int MaxRecSum(int n)
{
	for (int i = 0; i <= n; ++i)
	{
		p[i][0] = 0;
		p[0][i] = 0;
	}	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
			p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];
	}

	int max = INT_MIN;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; ++j)
		{
			int sum = 0;
			for (int k = 1; k <= n; ++k)
			{
				int temp = p[j][k] - p[j][k-1] - p[i-1][k] + p[i-1][k-1];
				if (sum > 0)
					sum += temp;
				else
					sum = temp;
				if (sum > max)
					max = sum;
			}
		}
	}
	return max;
}

int main()
{
	int n = 4;
	int num;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> num;
			a[i][j] = num;
		}
	}

	cout << MaxRecSum(n) << endl;
	return 0;
}