代码中使用了两种方法(solve1
和 solve2
)来解决最大子段和问题,solve1
通过分治法和结构体 Node
来保存区间信息,而 solve2
则是通过直接的递归加扫描区间来实现。Node
结构体中的四个属性分别保存了区间的不同信息,结合 operator+
实现分治法的区间合并。
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; } |