解題報告

題目描述

鏈接： POJ1050

給定一個二維數(shù)組，求這個二維數(shù)組的子數(shù)組中所有元素相加和最大的那個子數(shù)組，并且輸出這個子數(shù)組的和

輸入

第一行輸入一個整數(shù) N 代表二維數(shù)組的邊長
第二行輸入 N * N 個數(shù)代表數(shù)組的元素，以行優(yōu)先的方式來輸入

輸出

一個整數(shù)，代表最大子數(shù)組的和，一個輸出獨(dú)占一行

解題思路

一開始拿到題的思路是構(gòu)建一個四位數(shù)組dp[i][j][k][l]來存儲以a[i][j]為左上角，以a[k][l]為右下角的子數(shù)組的和，但是發(fā)現(xiàn)這樣的時間復(fù)雜度達(dá)到了O(n5)，肯定會超時。

后來查看網(wǎng)上的思路，發(fā)現(xiàn)可以轉(zhuǎn)換成一維最大子數(shù)組的和來求解：

假設(shè)子數(shù)組是從第 i 行到第 j 行，那么可以將 i 到 j 行壓縮成一行，即 i 到 j 行的所有列各自相加，問題就轉(zhuǎn)換成了一維最大子數(shù)組。

那么對于所有的 i 到 j 行，都壓縮一行求他們的最大子數(shù)組，所得結(jié)果之中最大的那個就是最終結(jié)果

Note：

1. colSum[i][j]為第 i 列從 0 到 j 行的和
2. 求一維數(shù)組的最大子數(shù)組偽代碼：

    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;
}