输入一个二维整形数组, 数组里有正数也有负数.
二维数组中连续的一个子矩阵组成一个子数组, 每个子数组都有一个和.
求所有子数组的和的最大值. 要求时间复杂度为 O(n).
两人结对完成编程任务.
一人主要负责程序分析, 代码编程. 一人负责代码复审和代码测试计划.
- #include
- using namespace std;
- #define M 1000
- int A[M][M];
- int AS[M][M];
- inline int ArraySum(int s,int t,int i,int j)
- {
- return AS[i][j]-AS[i][t-1]-AS[s-1][j]+AS[s-1][t-1];
- }
- int max(int a,int b)
- {
- return(a>b?a:b);
- }
- int main()
- {
- int m,n,i,j;
- cout<<"输入数组的行数:";
- cin>>n;
- cout<<"输入数组的列数:";
- cin>>m;
- cout<<"输入一个二维整数数组:"<<endl;
- for(i=0;i<n;i++)
- {
- for(j=0;j<m;j++)
- {
- cin>>A[i][j];
- }
- }
- for(i=0;i<n;i++)
- {
- for(j=0;j<m;j++)
- {
- AS[i][j]=A[i][j]+AS[i-1][j]+AS[i][j-1]-AS[i-1][j-1];
- }
- }
- int Max=A[0][0];
- for(int a=0;a<n;a++)
- {
- for(int c=a;c<n;c++)
- {
- int IV=ArraySum(a,0,c,0);
- for(j=1;j<m;j++)
- {
- IV=max(ArraySum(a,j,c,j),ArraySum(a,j,c,j)+IV);
- Max=max(IV,Max);
- }
- }
- }
- cout<<"数组最大子数组之和为:"<<Max<<endl;
- system("pause");
- }
来源: http://www.bubuko.com/infodetail-2816043.html