hdu1081dp

사고방식: 이 문 제 는 1 차원 최대 필드 와 2 차원 으로 확장 하 는 것 이다.
1 차원 알고리즘 은 이 렇 습 니 다.

int max_sum(int n)
{
    int i, j, sum = 0, max = -10000;
    for(i = 1; i <= n; i++)
    {
        if(sum < 0)
            sum = 0;
        sum += a[i];
        if(sum > max)
            max = sum;
    }
    return sum;
}

2 차원 으로 확장 할 때 도 같은 방법 이지 만 2 차원 을 1 차원 으로 압축 해 야 하기 때문에 우 리 는 데 이 터 를 처리 해 야 한다. map [i] [j] 가 i 행 의 j 번 째 요 소 를 표시 하 는 것 에서 i 행 앞의 j 번 째 요소 와 이렇게 map [k] [j] - map [k] [i] 를 표시 하면 k 행 이 i - > j 열 에서 의 요소 와.1 차원 보다 2 층 순환 매 거 진 i 와 j 만 있 으 면 됩 니 다.

/*****************************************
Author      :Crazy_AC(JamesQi)
Time        :2015
File Name   :
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#define MEM(a,b) memset(a,b,sizeof a)
#define pk push_back
template<class T> inline T Get_Max(const T&a,const T&b){return a < b?b:a;}
template<class T> inline T Get_Min(const T&a,const T&b){return a < b?a:b;}
typedef long long ll;
typedef pair<int,int> ii;
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 110;
int gg[maxn][maxn];
int n;
int main()
{	
	// ios::sync_with_stdio(false);
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	while(~scanf("%d",&n)){
		MEM(gg, 0);
		int buf;
		for (int i = 1;i <= n;++i) {
			for (int j = 1;j <= n;++j){
				scanf("%d",&buf);
				gg[i][j] += gg[i][j - 1] + buf;
			}
		}
		int Max_Num = -INF;
		for (int i = 1;i <= n;++i){
			for (int j = i;j <= n;++j){
				int sum = 0;
				for (int k = 1;k <= n;++k){
					if (sum < 0)
						sum = 0;
					sum += gg[k][j] - gg[k][i - 1];
					if (sum > Max_Num) Max_Num = sum;
				}
			}
		}
		printf("%d
",Max_Num);
	}
	return 0;
}