返回一个二维整数数组中最大子数组的和(头尾相接)

1.题目。

题目:返回一个二维整数数组中最大子数组的和。
要求：
输入一个二维整形数组，数组里有正数也有负数。
二维数组首尾相接，象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

2.设计思想。

分别求出每一行的最大子矩阵，然后再两行相加，求出最大子矩阵，一直到所有的行相加，求出最大子矩阵。比较其中最大的子矩阵值，找出最大的。

3.代码。

 1 #include<iostream>
 2 using namespace std;
 3 #include <ctime>
 4 #include <cstdlib>
 5 #define MAX 10000 
 6 int Max(int b[])
 7 {
 8     int m[MAX],n=0,p=0;
 9     for(int i=0;i<4;i++)
10     {
11         for(int j=0;j<4;j++)
12         {
13             n=n+b[i+j];
14             m[p]=n;
15             p++;
16         }
17         n=0;
18     }
19     int max=m[0];
20     for(i=0;i<p;i++)
21     {
22         if(m[i]>max)
23             max=m[i];
24     }
25     return max;
26 }
27 
28 int main()
29 {
30     int k[MAX],a[4][8],h[8];
31     srand(time(0));
32     cout<<"该矩阵为:"<<endl;
33     for(int i=0;i<4;i++)
34     {
35         for(int j=0;j<4;j++)
36         {
37             a[i][j]=rand()%100-50;
38             a[i][j+4]=a[i][j];
39             cout<<a[i][j]<<" ";
40         }
41         cout<<endl;
42     }
43     for(i=0;i<4;i++)
44     {
45         k[i]=Max(a[i]);
46     }
47     int  q=4;
48     for(i=0;i<3;i++)
49     {
50         int    t=0;
51         for(int j=0;j<8;j++)
52         {
53             
54             h[t]=a[i][j]+a[i+1][j];
55             t++;
56         }
57         k[q]=Max(h);
58         q++;
59     }
60     for(i=0;i<2;i++)
61     {
62         int    t=0;
63         for(int j=0;j<8;j++)
64         {
65             
66             h[t]=a[i][j]+a[i+1][j]+a[i+2][j];
67             t++;
68         }
69         k[q]=Max(h);
70         q++;
71     }
72     int t=0;
73     i=0;
74     for(int j=0;j<8;j++)
75     {
76         
77         h[t]=a[i][j]+a[i+1][j]+a[i+2][j]+a[i+3][j];
78         t++;
79     }
80     k[q]=Max(h);
81     q++;
82     cout<<endl;
83     int max=k[0];
84     for(i=0;i<q;i++)
85     {
86         if(k[i]>max)
87             max=k[i];
88     }
89     cout<<"最大子矩阵的值为:"<<endl;
90     cout<<max;
91     return 0;
92 }

4.运行结果。