백련 2766 최대 서브 매트릭스 [사유+dp사상]

전송문//제목의 뜻은 더 이상 말하지 않겠다.//사상: 행렬이라면 대칭적이다.그래서 우리는 한 2차원을 두 줄의 수를 더해서 1차원으로 볼 수 있다. 그러면 가장 큰 행렬과 사실은 1차원에서 가장 큰 연속과 합을 찾는 것이다.이렇게 나온 답은 바로 우리가 원하는 것이다.그래서 모든 가능한 O(n^3)의 복잡도를 매개적으로 제시한다.마지막 답이 마이너스일 수도 있으니,res의 초기 값을 0으로 설정하지 마십시오.

/** @Cain*/
const int maxn=1e2+5;
int a[maxn][maxn];
int dp[maxn];
int getMax(int *dp,int n)  //              .
{
    int tmp = 0,ans = dp[0]; 
 //             ,  ( )    ,           .
    for(int i=0;iif(tmp > 0) tmp += dp[i];
        else tmp = dp[i];
        ans = max(ans,tmp);
    }
    return ans;
}

void solve()
{
    int n;
    while(~scanf("%d",&n)){
        Fill(a,0);
        for(int i=0;ifor(int j=0;j"%d",&a[i][j]);
            }
        }
        int res = a[0][0];  //   .
        for(int i=0;i0);
            for(int j=i;jfor(int k=0;k"%d
",res);
    }
}