结对成员--张永&吴盈盈
写这篇博客的时候，心里很烦，不是因为这个题目，而是在建民老师要求的时间快到了的（2014.3.19 18:00），我这篇博客还在没发表完，更烦的是我那个烂电脑关键时候掉了链子。。。不过。。还得忍住万般痛苦，写下这抛砖引玉的博客。
首先，先说一下建民老师给的题目吧：大意是 给定一个二维数组，求出其中的值最大的子数组。 题目一下来，准备写程序。。。电脑竟然红屏了，什么情况，无奈就拖到了这个时候。 对于这个题目，每一个学过编程的人，都能快速的想出一种大众算法，叫做 暴力枚举法 吧。就是把所有的子数组的和都求出来，然后在找出其中和最大的那个子数组，把它输出到屏幕。这种算法实现起来简单，且很容易想到。但是它的效率很低。这是它最大的缺点。
我们是大学生，学过高等数学，这类的题目考的就是一个人的数学功底，但是哦，当面对这道题目的时候，我真的不想再说我学过高等数学了。。。。。。为了能够找到高效的算法。我和队友还是进行了很认真的探索，但是一些方法想想有点道理，但对自己就不知如何下手了。比如老师说找到这个二维数组的所有正数和负数的分布。然后根据这个分布确定最大值出现的可能性。。。。。。这个方法真的不知如何下手。思想上的挣扎总是在追求完美的时候表现的异常激烈。 在网上试着找了一些算法。看了看，贴在这里，也算是一个收集吧：
/* 首先遍历所有的行，即，用两平行条线划分X方向。这是O(N^2)的，然后将夹在中间的找可能的列看做一维上找最大的子序列和，只需O（M）时间。所以最终为O(N^2*M)效率 */
#include " stdafx.h "
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <queue>
#include <Windows.h>
using namespace std;
#define MAX 100
int N,M; // N*M
int arr[MAX][MAX];
int mem[MAX][MAX];
int memy[MAX];
int posybegin[MAX];
// 求子矩阵之和，利用预处理的部分和技术(x1,y1)左上角~(x2,y2)右下角 O(1)
int subMatrix( int x1, int y1, int x2, int y2)
{
return mem[x2][y2]-mem[x1- 1 ][y2]-mem[x2][y1- 1 ]+mem[x1- 1 ][y1- 1 ];
}
int _tmain( int argc, _TCHAR* argv[])
{
// 处理输入
while (cin>>N>> M)
{
for ( int i= 1 ;i<=N;i++ )
{
for ( int j= 1 ;j<=M;j++ )
{
cin >> arr[i][j];
}
}
// 初始化mem
memset(mem, 0 ,MAX* MAX);
// 快速预处理部分和 DP O(N*M) 部分和指的是mem[i][j]即（1,1）到（i,j）的矩阵和
for ( int i= 1 ;i<=N;i++ )
{
for ( int j= 1 ;j<=M;j++ )
{
mem[i][j] =mem[i- 1 ][j]+mem[i][j- 1 ]-mem[i- 1 ][j- 1 ]+ arr[i][j];
}
}
for ( int i= 0 ;i<=N;i++ )
{
for ( int j= 0 ;j<=M;j++ )
{
cout <<mem[i][j]<< " \t " ;
}
cout << endl;
}
cout << endl;
// 进行具体的解答最大子矩阵和 O(N^2*M^2)
int Max= INT_MIN;
int posx1,posx2,posy1,posy2;
// 先遍历所有可能的行
for ( int x1= 1 ;x1<=N;x1++ )
{
for ( int x2=x1;x2<=N;x2++ )
{
// 先在将题目看成一维的
// 1,初始化memy
memset(memy, 0 ,M+ 2 );
memy[ 1 ]=subMatrix(x1, 1 ,x2, 1 );
posybegin[ 1 ]= 1 ;
int max= INT_MIN;
int y1,y2;
// 2，DP获得在x1x2框架下的DP
for ( int y= 2 ;y<=M;y++ )
{
if (memy[y- 1 ]< 0 )
{
memy[y] = subMatrix(x1,y,x2,y);
posybegin[y] = y;
}
else
{
memy[y] =subMatrix(x1,y,x2,y)+memy[y- 1 ];
posybegin[y] =posybegin[y- 1 ];
}
}
// 3,在x1,x2夹缝中的最大值。
for ( int y= 1 ;y<=M;y++ )
{
if (memy[y]> max)
{
max = memy[y];
y1 = posybegin[y];
y2 = y;
}
}
// 4,将这个结果记录到整个的最大值中：
if (max> Max)
{
Max = max;
posx1 =x1;posx2=x2;posy1=y1;posy2= y2;
}
}
}
cout <<Max<< endl;
cout << " ( " <<posx1<< " , " <<posy1<< " ) " << endl;
cout << " ( " <<posx2<< " , " <<posy2<< " ) " << endl;
}
::system( " pause " );
return 0 ;
}
参考了以下这个算法，出自《编程之美》， 做了这两次的课上训练，感觉数学在IT领域真的很重要。希望大家能够提出一些意见供小弟参考，学习。
查看更多关于大牛，求一个最值，你能提出什么好的算法么的详细内容...