大家加油~~

re

kankan

~

/*
问题描述：
1。背景
一个在一维情况下很容易解决的问题，往往在多维情况下却很难解决。

2。问题
给定一个2维的整数矩阵，找出其中最大和的子矩阵，一个矩阵的和就是该矩阵中所有元素的和。
本题中具有最大和的子矩阵称为最大子矩阵。子矩阵是位于整个矩阵中任何一个1*1或更大的连续子矩阵，
例如，在矩阵
 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2
其中最大子矩阵在左下角：
 9 2
-4 1
-1 8
和为15

函数接口

int Func_(int a[][],int n);

接收一个n*n（n>=1&&n<=100）的整数矩阵，矩阵中元素取值在-127到127
返回最大子矩阵的和
24-06-06 17:32

*/
#include <iostream>
#include <time.h>

using namespace std;

const int N = 4;

int ColSum(const int a[][N], int low, int high, int col);
int MaxSum(const int a[][N], int n);

int main()
{
    time_t startTime;
    time_t endTime;
    time(&startTime);

      int a[N][N] ={{-90,-2,0,-70},
                     {-9,-2,-6,-2},
                     {-4,-1,-4,-1},
                     {-1,-8,-60,-2}};
      for (int i=0; i<5; i++)
            cout<<MaxSum(a, N)<<endl;

    time(&endTime);
    cout << difftime(endTime, startTime) << endl;

    getchar();
    return 0;
}
/*
函数介绍：求二维数组方阵中的最大子阵的和
输入：const int a[][N]，二维数组
      int n 数组的大小
输出：最大子阵的和
*/
int MaxSum(const int a[][N], int n)
{
      int max = 0;
      for (int i=0; i<n; i++)//i表示子阵的第一行在数组中的行号
      {
            for (int j=i; j<n; j++)//j表示子阵的最后一行在数组中的行号
            {
                  int sum = 0; //累积子阵的和
                  for (int k=0; k<n; k++)//用动态规划的方法计算拥有j-i+1行的子阵的最大和
                  {
                        sum += ColSum(a, i, j, k);//计算拥有j-i+1行的子阵的第k+1列的和
                        if (sum > max)
                              max = sum;
                        else if (sum < 0)
                              sum = 0;
                  }
            }
      }
      if (max == 0) //处理当矩阵的所有元素值均小于或等于0的情况
      {
            max = -127;
            for (int i=0; i<n; i++)
                  for (int j=0; j<n; j++)
                        if (a[i][j] > max)
                              max = a[i][j];
      }
      return max;
}

/*
函数介绍：求二维数组方阵中拥有high-low+1行的子阵的第col+1列的和
输入：const int a[][N]，二维数组
      int low， 表示子阵的第一行在数组中的行号
      int high， 表示子阵的最后一行在数组中的行号
      int col，列号
输出：子阵的第col+1列的和
*/
int ColSum(const int a[][N], int low, int high, int col)
{
      int sum = 0;
      for (int i=low; i<=high; i++)
            sum += a[i][col];

      return sum;
}

哈哈,

*/*/

const int N = 100;
int Func_(int a[][N],int n)
{
    int i,j;
    int x1,y1,x2,y2;
    int max = -100000000,sum;
    for(x1=0;x1<n;x1++)
    for(y1=0;y1<n;y1++)
    for(x2=x1;x2<n;x2++)
    for(y2=y1;y2<n;y2++){
        sum = 0;
        for(i=x1;i<=x2;i++)
        for(j=y1;j<=y2;j++){
            sum += a[i][j];
        }
        max = (sum>max) ? sum : max;
        if(sum<0)
            break;
    }
    return max;
}

上面的有重复计算,
这个是临时写的,没测试,高考后每天只睡3小时，受不了了

const int N = 100;
int Func_(int a[][N],int n)
{
    int i,j;
    int x1,y1,x2,y2;
    int max = -100000000,sum,temp;
    for(x1=0;x1<n;x1++)
    for(y1=0;y1<n;y1++)
    for(x2=x1;x2<n;x2++){
        sum = 0;
        for(y2=y1;y2<n;y2++){
            temp = 0;
            for(i=x1;i<=x2;i++){
                temp += a[i][y2];
            }
            sum += temp;
            max = (sum>max) ? sum : max;
            if(sum<0)
                break;
        }
    }
    return max;
}

按时大苏打