【华为OD】C卷真题100分：最大矩阵和 C/C++代码实现[思路+代码]

JS、java、python、C代码：

【华为OD】C卷真题100分：最大矩阵和 JavaScript代码实现[思路+代码]-CSDN博客

【华为OD】C卷真题100分：最大矩阵和 Java代码实现[思路+代码]-CSDN博客

【华为OD】C卷真题100分：最大矩阵和 python代码实现[思路+代码]-CSDN博客

【华为OD】C卷真题100分：最大矩阵和 C语言代码实现[思路+代码]-CSDN博客 

题目描述：

给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。

输入描述:

输入的第一行包含2个整数n, m(1 <= n, m <= 10)，表示一个n行m列的矩阵，下面有n行，每行有m个整数，同一行中，每2个数字之间有1个空格，最后一个数字后面没有空格，所有的数字的在[-1000, 1000]之间。

输出描述:

输出一行一个数字，表示选出的和最大子矩阵内所有的数字和。

示例1输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3

输出

20

说明

一个3*4的矩阵中，后面3列的子矩阵求和加起来等于20，和最大。

     879                                                         
                                                            
              +—+                                                          
  3            |   |       ++                               +       +—|   
  |           |   | 3      +                6               +  |   +   |        +
  |      +     |   |       +         +                      +    |  +   |       +
  |      +    |   +—+    +        +        +++++          +   +  +   |        +
  |      +    | +      |   +   +—-+        |   |          +   +  +   |        +
  |      +  3 | +      |   +   +    +      2 |   |     2    +   +  +   |        +
  |      +    | +      |   +   +    +        |   |          +   +  +   |        +
  |      +—+ +     |    |  |    +    —-+   |   +—+    |  |  +   |         +
  |      |     +     |    |  |    +    |       |   |   |    |  |  +   |         +
  |    1 |     +     | 8  |  |    +  1 |   |    | 1 |   | 1 |   |  +   |        +
  |      |     +     |    |  |    +    |   |    |   |   |   |   |  +   |        +
  |  +—+     +     +—+   |    ++—+    ++   +—+   +—+   |  +   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  |0 |         +         | 0 |  0 |         ++              | 0 |  |+   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  +—+         +          +——-+                       +—+| +|+   |        +
                +                                                    +   |        +
    0   1   2   3   4   5   6   7   8   9  10  11  12 + v:    w  u m    u 1 0 2 4
 

题目解析：

        使用循环来处理即可

代码实现：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void initData(vector<vector<int>> &data, int &row, int &col) {
    cin >> row >> col;
    for (int i = 0; i < row; i++) {
        vector<int> subArr(col);
        for (int j = 0; j < col; j++) {
            cin >> subArr[j];
        }
        data.push_back(subArr);
    }
}

int calcSum(const vector<vector<int>> &data, int a, int b, int r, int c) {
    int sum = 0;
    for (int i = a; i < r + 1; ++i) {
        for (int j = b; j < c + 1; ++j) {
            sum += data[i][j];
        }
    }
    return sum;
}

int getRet(const vector<vector<int>> &data, const int &row, const int &col) {
    int ret = -1000 * 1000;
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            for (int r = i; r < row; ++r) {
                int tempVal = -1000 * 1000;
                for (int c = j; c < col; ++c) {
                    tempVal = max(calcSum(data, i, j, r, c), tempVal);
                }
                ret = max(ret, tempVal);
            }
        }
    }
    return ret;
}

int main() {
    int row;
    int col;
    vector<vector<int>> data;
    initData(data, row, col);
    int ret = getRet(data, row, col);
    cout << ret << endl;
    return 0;
}