返回一个二维整形数组最大子数组的和

题目：返回一个二维整数数组中最大子数组的和

 作业要求：

 1、输入一个二维整形数组，数组里有正数有负数。

 2、二维数组中连续的一个子矩阵组成一个子数组。

3、求所有子数组的和的最大值。

思路

   先用求一维数组最大子数组之和的方法，求最大值，然后再算相邻两行最大子数组的和/相邻行同列相加，会得到一个新的一维数组，依次计算比较往下面求。最终得到二维数组最大子数组的和

代码

#include <iostream>
#include <time.h>
using namespace std;
#define M 4
#define N 8

void main()
{
int a[M][N],b[N],c = 0,d = 0;
int maxc ,maxd,end1[M][N] = {0},end2[M][N] = {0};
int i_max = 0,j_max = 0;

srand((unsigned int)time(0));

for (int j = 0;j < M;j++)
{
for (int k = 0;k < N;k++)
{
a[j][k] = rand()%100 - 50;
cout << a[j][k] << " ";
}
cout << endl;
}
cout << endl;

maxc = a[0][0];
maxd = a[0][0];
for (int i = 0;i < M;i++)
{
for (int i_hang = 0;i_hang < M-i;i_hang++)
{
for (int j = 0;j < N;j++)
{
b[j] = 0;
}
for (int i_hang1 = i_hang;i_hang1 <= i_hang+i;i_hang1++)
{
for (int j = 0;j < N;j++)
{
b[j] += a[i_hang1][j];
}
}
c = 0;
for (int k = 0;k < N;k++)
{
c += b[k];
if (c > maxc)
{
maxc = c;
end1[i][i_hang] = k;
i_max = i;
j_max = i_hang;
}
if(c < 0)
{
c = 0;
}
}

for (int p= N-1;p >= 0;p--)
{
d += b[p];
if (d > maxd)
{
maxd = d;
end2[i][i_hang] = p;
}
if(d < 0)
{
d = 0;
}
}

}
}
cout << "子数组为：" << endl;
for (int k = 0;k <= i_max;k++)
{
for (int k1 = end2[i_max][j_max];k1 <= end1[i_max][j_max];k1++)
{
cout << a[j_max+k][k1] << " ";
}
cout << endl;
}

cout << endl;
cout << "和为： " << maxd << endl;
}

总结：不想拍照

返回一个二维整形数组最大子数组的和

原文：https://www.cnblogs.com/guci/p/9825133.html