#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,接下来继续加上第三行,以此类推,直到加到最后一行。
感受:难,还是不能够找到很好的思路,虽然从网上百度到了,但可能还有瑕疵,对于b小于0的判断可能还有问题。
成员:宋雨佳,周雪莹
原文:http://www.cnblogs.com/xiangwo/p/4403612.html