#include<iostream>
#define N 5
using namespace std;
int main()
{
int a[4][5]={1,2,-1,-4,-20,-8,-3,4,2,1,3,8,10,1,3,-4,-1,1,7,-6},i,j;
for(i=0;i<N-1;i++)
{
for(j=0;j<N;j++)
{cout<<a[i][j]<<" ";}
cout<<endl;
}cout<<endl;///////////////////////////////////数组输出
int sum=a[0][0],b,c[N];
int imin=0,imax=0,jmin=0,jmax=0;
for(i=0;i<N;i++)
c[i]=a[0][i];
for(i=1;i<=4;i++)
{
b=c[0];
for(int j=1;j<N;j++)
{
if(b<0)
{ b=c[j];jmin=j;}
else
b+=c[j];
if(sum<=b)
{ sum=b;jmax=j;}
}
if(i<N-1)
{
if(b<0)
{
for(int j=0;j<N;j++)
{c[j]=a[i][j];imin=i;}
}
else
{
for(int j=0;j<N;j++)
{
c[j]+=a[i][j];
imax=i;
}
}
}
}
for(i=imin;i<=imax;i++)
{
for(j=jmin;j<=jmax;j++)
{cout<<a[i][j]<<" ";}
cout<<endl;
}cout<<endl;
cout<<sum<<endl;
}
思路:把每行看成一维数组来做,先求第一行的最大子数组的和,赋值给b,然后加上第二行变成一个新的一维数组,继续求和,若和b大于sum,则sum更新,若b小于0则舍弃该行,im,in等于i,接下来继续加上第三行,以此类推,直到加到最后一行。
感受:没有思路,还是看的学长们的思路,本来想抄他们的程序,结果测试发现他们程序有错。。。给评论了也不知道他们看见没,后来还是用的他们的思路,程序是宋雨佳编的,还是觉得思路很重要。
成员:宋雨佳,周雪莹
原文:http://www.cnblogs.com/xiaowumao/p/4403662.html