二维整形数组的最大子数组和（结对作业）

  1 #include<iostream>
  2 using namespace std;
  3 int sum_Array_lift(int **p,int m,int n,int r,int le);
  4 int sum_Array_right(int **p,int m,int n,int r,int le);
  5 int max_shu(int a,int b);
  6 int main()
  7 { 
  8   int m,n,max_sum=0;
  9   //实现整型数组的输入
 10   cout<<"输入整型数组的行长度 ";
 11   cin>>m;
 12   cout<<"输入整型数组的列长度 ";
 13   cin>>n;
 14   //创建一个二维数组
 15   int ** p;
 16   p = new int *[m];
 17   for (int i = 0; i <m; i++)
 18   {
 19       p[i] = new int[n];
 20   }
 21   cout<<"输入一个二维整型数组"<<endl;
 22   for(int i=0;i<m;i++)
 23   {
 24       for(int j=0;j<n;j++)
 25       {    
 26           cin>>p[i][j];
 27       }
 28   }
 29   int r=0,le=0,k1=0,k2=0;
 30   max_sum=sum_Array_lift(p,m,n,r,le);
 31   while(r!=m&&le!=n)
 32   {
 33       if(r!=m)
 34       {
 35           r++;
 36           k1=max_shu(sum_Array_lift( p, m, n,r, le),sum_Array_right( p, m, n,r, le));//比较从第r行切和第n-1-r行切的值，取最大的给k1
 37           r--;
 38       }
 39       if(le!=n)
 40       {
 41           le++;
 42           k2=max_shu(sum_Array_lift( p, m, n,r, le),sum_Array_right( p, m, n,r, le));//比较从第le列切和第n-1-le列切的值，取最大的给k2
 43           le--;
 44       }
 45       if(max_sum<max_shu(k1,k2))//让max_sum取k1和k2的最大值
 46       {
 47           max_sum=max_shu(k1,k2);
 48       }
 49       if(k1>k2)
 50       {
 51           r++;
 52           if(sum_Array_lift( p, m, n,r, le)<sum_Array_right( p, m, n,r, le))//为了不让空间复杂度增加，我们通过改变矩阵的值 使得等同于切割后的矩阵
 53           {
 54                for(int j=0;j<n;j++)
 55               {
 56                   for(int i=m-1;i>=r;i--)
 57                   {
 58                       p[i][j]=p[i-1][j];
 59                   }
 60               }
 61           }
 62           r--;
 63       }
 64       else 
 65       {
 66           le++;
 67           if(sum_Array_lift( p, m, n,r, le)<sum_Array_right( p, m, n,r, le))//为了不让空间复杂度增加，我们通过改变矩阵的值 使得等同于切割后的矩阵
 68           {
 69               for(int i=0;i<m;i++)
 70               {
 71                   for(int j=n-1;j>=le;j--)
 72                   {
 73                       p[i][j]=p[i][j-1];
 74                   }
 75               }
 76           }
 77           le--;
 78       }
 79       if(r!=m)
 80       {
 81           r++;
 82       }
 83       if(le!=n)
 84       {
 85           le++;
 86       }
 87       if(k1>k2)
 88       {
 89           le--;
 90       }
 91       else r--;
 92   }
 93   cout<<"二维数组最大子数组之和为 "<<max_sum<<endl;
 94   return 0;
 95 }
 96 int sum_Array_lift(int **p,int m,int n,int r,int le)
 97 {
 98     int sum=0;
 99     for(int i=r;i<m;i++)
100     {
101         for(int j=le;j<n;j++)
102         {
103             sum=sum+p[i][j];
104         }
105     }
106     return sum;
107 }
108 int max_shu(int a,int b)
109 {
110     if(a>b)
111     {
112         return a;
113     }
114     else return b;
115 }
116 int sum_Array_right(int **p,int m,int n,int r,int le)
117 {
118     int sum=0;
119     for(int i=m-1-r;i>=0;i--)
120     {
121         for(int j=n-1-le;j>=0;j--)
122         {
123             sum=sum+p[i][j];
124         }
125     }
126     return sum;
127 }

 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 int A1[5][5];
 5 int max(int a, int b)
 6 {
 7     if (a > b)
 8         return a;
 9     else
10         return b;
11 }
12 int min(int a, int b)
13 {
14     if (a > b)
15         return b;
16     else
17         return a;
18 }
19 int findmax(int m[1000])
20 {
21     int max = m[0];
22     for (int i = 0; i<1000; i++)
23         if (m[i]>max)
24             max = m[i];
25     return max;
26 }
27 int sum(int x, int y, int x1, int y1)
28 {
29     int sum = 0;
30     int i, j;
31     int maxx = max(x, x1);
32     int maxy = max(y, y1);
33     int minx = min(x, x1);
34     int miny = min(y, y1);
35     for (i = minx; i <= maxx; i++)
36         for (j = miny; j <= maxy; j++)
37             sum = sum + A1[i][j];
38     return sum;
39 }
40 int findmaxarry(int A[5][5])
41 {
42     int M[1000] = { 0 }; int i = 0;
43     int a, b, c, d;
44     for (a = 0; a<5; a++)
45         for (b = 0; b<5; b++)
46             for (c = 0; c<5; c++)
47                 for (d = 0; d<5; d++)
48                 {
49                     if (a == c&&b == d)
50                     {
51                         M[i] = A[a][b]; i++;
52                     }
53                     else
54                     {
55                         M[i] = sum(a, b, c, d); i++;
56                     }
57                 }
58     return findmax(M);
59 }
60 int main()
61 {
62     
63     
64     for (int i = 0; i < 5; i++)
65     {
66         for (int j = 0; j < 5; j++)
67         {
68             cin >> A1[i][j];
69         }
70     }
71     int AllMax;
72     AllMax = findmaxarry(A1);
73     cout << AllMax << endl;
74     system("pause");
75 }

 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 int Max(int A[100],int &Max)                       //求较数组中最大值
 5 {
 6     int Max1 = A[0];
 7     
 8     for (int i = 0; i < 100; i++)
 9     {
10         if (Max1 < A[i])
11             Max1 = A[i];
12     }
13     return Max1;
14 }
15 int Addt(int **p, int i,int j)//求矩阵i*j的和的最大值
16 {
17     int sum,sum1,sum2;
18     
19     for (int m = 0; m < 5; m++)
20     {
21         if (m + i >= 5)
22             break;
23         else
24         { 
25             for (int n=0; n < 5; n++)//先确定p【m】【n】，再通过m，n的固定求和；
26             {
27                 sum1 = 0; sum2 = p[m][n];
28             if (n + j >= 5)
29                 break;
30             else
31             { for (int m1 = 0; m1 < i; m1++)
32                {
33                 for (int n1 = 0; n1 < j; n1++)
34                   {
35                       sum1 = sum1 + p[m + m1][n + n1];  
36                       if (sum2 < sum1)
37                       {
38                           sum2 = sum1;
39                           sum = sum1;
40                       }
41                   }
42                }
43           
44             }    
45         }
46         }
47         
48     }
49 
50     return sum;
51 }
52 int main()
53 {
54     int i, j;
55     cout << "输入行数：";
56     cin >> i;
57     cout << "输入列数：";
58     cin >> j;
59     int **p;
60     p = new int *[i];
61     for (int m = 0; m < i; m++)
62     {
63         p[m] = new int[j];
64     }
65     for (int m = 0; m < i; m++)
66     {
67         for (int n = 0; n < j; n++)
68         {
69             cin >> p[m][n];
70         }
71     }
72     int B1[20], a = 0;
73     for (int i = 0; i < 5; i++)
74     {
75         for (int j = 0; j < 4; j++)
76         {
77             B1[a] = Addt(p, i, j);//将i*j矩阵最大值赋给B【a】
78             a = a + 1;
79         }
80     }
81     int t;
82     cout << Max(B1,t)<<endl;
83     system("pause");
84 }