首页 > 其他 > 详细

UVA108 - Maximum Sum(最大连续和)

时间:2014-08-01 23:16:52      阅读:406      评论:0      收藏:0      [点我收藏+]

题意:从一个n*n的矩阵中找出和最大的子矩阵


思路:最大连续和的求解。我们可以将二维的转化为一维进行计算。sum[i][j]表示以(1, 1)和(i, j)为对角的矩阵的和。之后只要逐个枚举每个可能出现的值,保存最大值即可


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int arr[MAXN][MAXN], sum[MAXN][MAXN], s[MAXN][MAXN];

int main() {
    int n;    
    while (scanf("%d", &n) != EOF) {
        memset(s, 0, sizeof(s));
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) {
                scanf("%d", &arr[i][j]);  
                s[i][j] = s[i][j - 1] + arr[i][j];
            }

        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) 
                sum[i][j] = sum[i - 1][j] + s[i][j];
        } 

        int Max = -INF;
        for (int i = 1; i <= n; i++) {  
            for (int j = 0; j < i; j++) {  
                int t, Min;  
                Min = 0;  
                for (int k = 1; k <= n; k++) {  
                    t = sum[i][k] - sum[j][k] - Min;  
                    if (t > Max) 
                        Max = t;  
                    if (sum[i][k] - sum[j][k] < Min)  
                        Min = sum[i][k] - sum[j][k];  
                }  
            }  
        }  
        printf("%d\n", Max);
    }
    return 0;
}

                                                 

UVA108 - Maximum Sum(最大连续和),布布扣,bubuko.com

UVA108 - Maximum Sum(最大连续和)

原文:http://blog.csdn.net/u011345461/article/details/38341579

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!