프로그래밍의 아름다움 - 하위 그룹의 합계 최대값 (2차원)

폭력적인 매거 방법을 피하고 우리는 1차원 수조의 구법을 참고한다. 1차원 해답은 재선형 시간 안에 완성할 수 있고 구체적으로는 나의 프로그래밍 주옥 독서 노트를 참고할 수 있다.
우리는 문제를 2차원에서 1차원으로 바꾸었다. 현재 우리는 행렬의 상하 경계를 매거한 다음에 1차원의 방법으로 좌우 경계를 확정한다. 시간의 복잡도는 O (N^2*M) 이다.

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=505;
int matrix[maxn][maxn];
int ps[maxn][maxn];			//    
int maxnum=-0xfffff;
int mmax(int a,int b)
{
	return a>b?a:b;
}
int BC(int row,int col,int m)  // row   col     m        
{
	return ps[col][m]-ps[row-1][m]-ps[col][m-1]+ps[row-1][m-1];
	
}
int maxsum(int matrix[maxn][maxn],int n,int m)
{
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
		{
			int maxendinghere=0,maxsofar=0; //           
			for(int k=1;k<=m;k++)           
			{
				maxendinghere=mmax(maxendinghere+BC(i,j,k),0);
				maxsofar=mmax(maxsofar,maxendinghere);
			}
			if(maxsofar>maxnum)maxnum=maxsofar;
		}
		return maxnum;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>matrix[i][j];
	memset(ps,0,sizeof(ps));
	for(int i=1;i<=n;i++)     //        ，   O(1)      BC（） 
		for(int j=1;j<=m;j++)
			ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+matrix[i][j];
	cout<<maxsum(matrix,n,m)<<endl;
	return 0;		
					
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

프로그래밍의 아름다움[02]_계속하다

2. 제목: 많은 무질서한 수 중에서 (먼저 서로 같지 않다고 가정하고) 그 중에서 가장 큰 K개의 수를 선택한다. 1. 빠른 배열의 분치 사상을 채택하여 먼저 무서수 중의 랜덤수를 취하여 무서수를 1, 2 두 부분...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

프로그래밍의 아름다움 - 하위 그룹의 합계 최대값 (2차원)

좋은 웹페이지 즐겨찾기