阅读程序-2解析

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

/**************************************************************** 
 * Description: 2021_S_R3
 * Author: Alex Li
 * Date: 2023-09-09 19:32:42
 * LastEditTime: 2024-09-15 00:03:16
****************************************************************/
#include <algorithm>
#include <iostream>
using namespace std;

int n, a[1005]; // 定义数组 `a` 和变量 `n` 用于存储输入数据和数组长度

// 定义结构体 Node 用于存储区间信息
struct Node
{
    int h, j, m, w; // h 表示区间最大前缀和, j 表示区间最大子段和, m 表示区间最大后缀和, w 表示区间元素和

    // 构造函数，用于初始化节点的四个值
    Node(const int _h, const int _j, const int _m, const int _w):
    h(_h), j(_j), m(_m), w(_w)
    { }

    // 运算符重载：定义两个 Node 之间的“+”操作，即将两个区间合并，计算合并后新的 h、j、m、w 值
    Node operator+ (const Node &o) const
    {
        // 合并两个区间时需要更新 h, j, m, w 的值
        return Node(
            max(h, w + o.h), // 合并后的最大前缀和 = 左区间的最大前缀和和（左区间和 + 右区间最大前缀和）的较大值
            max(max(j, o.j), m + o.h), // 合并后的最大子段和 = 左区间最大子段和、右区间最大子段和、左区间最大后缀和+右区间最大前缀和 三者中的最大值
            max(m + o.w, o.m), // 合并后的最大后缀和 = 左区间最大后缀和 + 右区间和 与 右区间最大后缀和中的较大值
            w + o.w // 合并后的区间和 = 左区间和 + 右区间和
        );
    }
};

// 递归求解最大子段和的函数，返回值为结构体 Node
Node solve1(int h, int m)
{
    if (h > m) // 如果左边界大于右边界，返回所有值为 -1 的 Node
        return Node(-1, -1, -1, -1);
    if (h == m) // 如果区间长度为 1，直接返回该单个元素的 Node，其中 h, j, m 取值为该元素的非负值，w 为元素的原值
        return Node(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);
    int j = (h + m) >> 1; // 取区间中点
    // 分治法：递归地计算左半区间和右半区间，合并两个区间
    return solve1(h, j) + solve1(j + 1, m);
}

// 另一种递归求解最大子段和的函数，返回值为整数
int solve2(int h, int m)
{
    if (h > m) // 如果左边界大于右边界，返回 -1
        return -1;
    if (h == m) // 如果区间长度为 1，返回该元素的非负值
        return max(a[h], 0);
    int j = (h + m) >> 1; // 取区间中点
    int wh = 0, wm = 0; // wh 表示左区间的最大后缀和，wm 表示右区间的最大前缀和
    int wht = 0, wmt = 0; // wht 和 wmt 分别用于记录后缀和和前缀和的临时变量
    // 从中点开始向左扫描，计算左区间的最大后缀和
    for (int i = j; i >= h; i--) {
        wht += a[i];
        wh = max(wh, wht);
    }
    // 从中点右侧开始向右扫描，计算右区间的最大前缀和
    for (int i = j + 1; i <= m; i++) {
        wmt += a[i];
        wm = max(wm, wmt);
    }
    // 返回左区间最大子段和、右区间最大子段和，以及跨越左右区间的最大子段和的最大值
    return max(max(solve2(h, j), solve2(j + 1, m)), wh + wm);
}

int main(){
    cin >> n; // 读取输入的数组长度
    for (int i = 1; i <= n; i++) cin >> a[i]; // 读取数组元素
    cout << solve1(1, n).j << endl; // 输出通过结构体 Node 方法求解的最大子段和
    cout << solve2(1, n) << endl; // 输出通过传统递归方法求解的最大子段和
    return 0;
}