【每日一题23】AcWing 126. 最大的和

发表于 更新于 分类于 Valine：
本文字数： 57 阅读时长 ≈ 1 分钟

Day23 AcWing 126. 最大的和

思路

  1. 前缀和
  2. 枚举
1
2
3
4
0 -2 -7  0
9  2 -6  2
-4 1 -4  1
-1 8  0 -2
1
2
3
4
5
6
7
8
 [i-1] [k]
 0  -2 -7  0 
 i
 9   2 -6  2 

-4   1 -4  1 
 j   k
-1   8  0 -2  [j][k]

类似题目

  1. 一维版本 55. 连续子数组的最大和
  2. 1051. 最大的和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int g[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            cin >> g[i][j];
            g[i][j] += g[i - 1][j];
        }

    int res = INT_MIN;
    for (int i = 1; i <= n; i ++ )  //上界
        for (int j = i; j <= n; j ++ )  //下界
        {
            int last = 0;
            for (int k = 1; k <= n; k ++ )  //向右枚举
            {
                last = max(last, 0) + g[j][k] - g[i - 1][k]; 
                //g[j][k]为一维数组枚举的每个元素 g[i-1][k]为上界上方的元素
                //减去之后的前缀和才是当前上下界矩阵的前缀和
                res = max(res, last);
            }
        }

    cout << res << endl;
    return 0;
}