二维数组求最大子数组

浏览数：26 / 时间：2015年06月08日

一、题目要求

程序要使用的数组放在一个叫 input.txt 的文件中, 文件格式是:

　　数组的行数,

　　数组的列数,

　　每一行的元素, (用逗号分开)

　　每一个数字都是有符号32位整数, 当然, 行数和列数都是正整数。

二、设计思想

算法思想：对于一维的数组，我们可以很容易用动态规划的方法求得最大子数组；

所以我们将i=[0...n], j[i..n]枚举所有行的可能，然后再对每一种可能（此时可以将它看做是一维数组的情况），用DP求得其最大子数组。

算法时间复杂度o(n^3)。

三、源代码

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<assert.h>
using namespace std;
//by frank
const int N = 103;
const int INF = -9999;
int maxSubArray(int a[], int n)
{
    assert(a!=NULL && n>0);
    int cur = 0;
    int max = INF;
  
    for(int i=0; i<n; i++)
    {
        cur += a[i];
  
        //当cur小于0时，应该重新开始计数.
        if(cur < 0)
            cur = 0;
  
        if(cur > max)
            max = cur;
    }
    return max;
}
  
int findMaxSubMatrix(int a[][N], int n)
{
    int tmpSum[N];
    int max = INF;
  
    //枚举所有行的可能组合。
    for(int i=0; i<n; i++)
    {
        //将tmpSum清零。
        memset(tmpSum,0,sizeof(tmpSum));
        for(int j=i; j<n; j++)
        {
            //加上当前行的元素。
            for(int k=0; k<n; k++)
                tmpSum[k] += a[j][k];
            int tmpMax = maxSubArray(tmpSum, n);
            if(tmpMax > max)
                max = tmpMax;
  
        }
    }
    return max;
}
  
int main()
{
    int a[N][N];
    int n = 0;
  
    while(cin>>n && n)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>a[i][j];
        cout<<findMaxSubMatrix(a, n)<<endl;
    }
      
    return 0;
}

四，运行结果截图