大牛，求一个最值，你能提出什么好的算法么

结对成员--张永&吴盈盈

写这篇博客的时候，心里很烦，不是因为这个题目，而是在建民老师要求的时间快到了的（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领域真的很重要。希望大家能够提出一些意见供小弟参考，学习。

大牛，求一个最值，你能提出什么好的算法么

推荐阅读