解题报告
题目描述
链接: 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:
-
colSum[i][j]
为第 i 列从 0 到 j 行的和 - 求一维数组的最大子数组伪代码:
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;
}