최대 하위 행렬의 합

제목 설명

알려진 행렬의 크기는 행렬의 모든 요소의 합으로 정의됩니다.행렬을 정하십시오. 가장 큰 비공개 (최소 11) 행렬을 찾는 것이 임무입니다.예를 들어 다음과 같은 44자 행렬 0-2-7 0 9 2 - 6 2 - 4 1 - 4 1 - 4 1 - 1 8 의 최대 자 행렬은 9 2 - 4 1 - 18 이 자 행렬의 크기는 15이다.

입력

각 수의 범위가 -127~127 사이인 N*N(1<=N<=100)의 정수 행렬을 입력합니다.

출력

최대 하위 행렬의 크기를 출력합니다.

샘플 가져오기

4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2

출력 예제

15

문제풀이의 방향

먼저 수조로 모든 수의 접두사와 접두사를 구한 다음에 모든 열을 하나의 전체로 보고 마지막에 최대 연속 수열로 최대 행렬의 합을 계산한다.

#include
#include
using namespace std;
int n,a[128][128],ans=-2147483647,b;//ans          ，
//            
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
          scanf("%d",&b);
          a[i][j]=a[i-1][j]+b;//        
       }
          for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)//     、   
			{
              int c=0;
                for(int k=1;k<=n;k++)
				{
                  c+=a[j][k]-a[i-1][k];//      
                  ans=max(ans,c);//          
                  c=max(c,0);//       0，     0，     0
		     	}
			}
      printf("%d",ans);
  return 0;
}