解题报告

题目描述

链接： POJ1050

给定一个二维数组，求这个二维数组的子数组中所有元素相加和最大的那个子数组，并且输出这个子数组的和

输入

第一行输入一个整数 N 代表二维数组的边长
第二行输入 N * N 个数代表数组的元素，以行优先的方式来输入

输出

一个整数，代表最大子数组的和，一个输出独占一行

解题思路

一开始拿到题的思路是构建一个四位数组dp[i][j][k][l]来存储以a[i][j]为左上角，以a[k][l]为右下角的子数组的和，但是发现这样的时间复杂度达到了O(n5)，肯定会超时。

后来查看网上的思路，发现可以转换成一维最大子数组的和来求解：

假设子数组是从第 i 行到第 j 行，那么可以将 i 到 j 行压缩成一行，即 i 到 j 行的所有列各自相加，问题就转换成了一维最大子数组。

那么对于所有的 i 到 j 行，都压缩一行求他们的最大子数组，所得结果之中最大的那个就是最终结果

Note：

1. colSum[i][j]为第 i 列从 0 到 j 行的和
2. 求一维数组的最大子数组伪代码：

    for(int i=0;i<length;i++){
        sum += a[i];
        if(sum < 0){
            sum = 0;
        }
    }
   

代码

#include <iostream>
#include <stdio.h>
#define MAX 100

using namespace std;

int a[MAX][MAX];
int colSum[MAX][MAX]={0};

int main(){
    int N;
    cin >> N;
    int result=-100000;
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            scanf(" %d" , &a[i][j]);
            if(i==0){
                colSum[j][i] = a[i][j];
            }
            else {
                colSum[j][i] = colSum[j][i-1] + a[i][j];
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=i;j<N;j++){
            int temp=0;
            for(int k=0;k<N;k++){
                if(i==0 || j==i){
                    temp += colSum[k][j];
                    if(temp < 0){
                        temp = 0;
                    }
                }
                else{
                    temp += colSum[k][j] - colSum[k][i-1];
                    if(temp < 0){
                        temp = 0;
                    }
                }
                if(temp > result){
                    result = temp;
                }
            }

        }
    }
    cout<<result<<endl;
}