二维最大和子数组

1、设计思路

因为计算了一位的最大和子数组，所以想办法将二维的数组转换成一维子数组进行求解；

首先，将二维数组的第一行（列）赋值到新的一维数组中，在一维的数组中求得子数组的最大值，

然后，将二维数组的第二行（列）加到一维数组中，再次求得子数组的最大值，并和第一步求得的最大值进行比较，若新的值比较大，留下最大值，如果新值比较小，退出这一个循环，从第二行（列）开始第一步，这样就可以求出最大和子数组；

2、源代码

#include<iostream>

#include<ctime>

using namespace std;

int main()

{

         int m, n;                      //数组大小

         int i, j, p, q, o;                //循环变量

         int a[100][100];               //数组

         int sh, x;                     //数值范围

         int sum, sum1 = -100, sum2 = -100;     //计算和

         int max = a[0][0];             //最大值

         int s[100];                    //转化成的一位数组

         int k = 0;                     //控制行数的变量

         cout << "请输入矩阵的行列数(上限100):";

         cin >> m >> n;

         cout << "请输入数值范围(a-b):" << endl;

         cin >> sh >> x;

         cout << "原矩阵为：" << endl;

         srand((unsigned)time(NULL));

         for (i = 0; i<m; i++)

         {

                   for (j = 0; j<n; j++)

                   {

                            a[i][j] = rand() % (x - sh + 1) + sh;

                            cout << a[i][j] << "  ";

                   }

                   cout << endl;

         }

         for (j = 0; j<n; j++)

         {

                   s[j] = 0;

         }

         for (i = 0; i<m; i++)

         {

                   while (k + i<m)

                   {

                            for (j = 0; j<n; j++)

                            {

                                     s[j] = s[j] + a[k + i][j];

                            }

                            for (p = 0; p < n; p++)

                            {

                                     for (q = 0; q <= p; q++)

                                     {

                                               sum = s[0];

                                               for (o = q+1; o <= p; o++)

                                                        sum = sum + s[o];

                                              if (sum > sum1)

                                               {

                                                        sum1 = sum;

                                               }

                                     }

                                     if (sum1 > sum2)

                                     {

                                               sum2 = sum1;

                                     }

                            }

                            if (sum2 > max)

                            {

                                     max = sum2;

                            }

                            k++;

                   }

                   k = 0;

                   for (j = 0; j<n; j++)

                   {

                            s[j] = 0;

                   }

         }

         cout << "和最大子矩阵值为" << max << endl;

         return 0;

}

3、程序截图：

4、总结：

将复杂的问题转换为比较简单的问题，编写程序时先把整个过程想明白，明白每一步怎样进行，然后将自然语言翻译成程序语言，我认为这是一个比较好的编写程序的方法。