洛谷P1121题解:动态规划求解环形数组最大子段和问题(附代码注释)
一、题目解读
洛谷P1121题要求求解环形数组的最大子段和,即在一个环形数组中找到一个连续子段,使其元素和最大。环形数组的特殊性在于首尾元素可相连,需考虑线性子段与跨越首尾的环形子段两种情况。
二、解题思路
采用动态规划,分“线性情况”与“环形情况”处理。
1. 线性情况:通过两次遍历,分别计算从左到右、从右到左的最大子段和(前缀和、后缀和),并组合两者得到不跨越首尾的最大线性子段和。
2. 环形情况:利用“总和-最小子段和”的策略,计算环形子段和。通过两次反向计算最小子段和,得到跨越首尾的最大环形子段和。
3. 特殊处理:若数组全为负数,直接返回最大元素。
三、解题步骤
1. 读取输入并计算元素总和。
2. 计算线性情况:
○ 从左到右动态更新当前最大子段和(prefix_max)。
○ 从右到左动态更新当前最大子段和(suffix_max)。
○ 遍历组合两者的和,得到线性情况最大值。
3. 计算环形情况:
○ 类似线性情况,计算最小子段和(prefix_min, suffix_min)。
○ 遍历时通过总和尚前缀和+后缀和得到环形子段和,并取最大值。
4. 比较线性与环形结果,返回较大者。
四、代码与注释
#include <iostream> #include <vector> #include <climits> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); int total = 0; // 读取输入并计算总和 for (int i = 0; i < n; ++i) { cin >> a[i]; total += a[i]; } // 情况1:线性情况(两段都在同一侧) int max_single = INT_MIN; vector<int> prefix_max(n), suffix_max(n); // 从左到右计算最大子段和 int current = 0; for (int i = 0; i < n; ++i) { current = max(a[i], current + a[i]); // 动态更新当前最大子段 max_single = max(max_single, current); prefix_max[i] = max_single; // 记录前缀最大值 } // 从右到左计算最大子段和 max_single = INT_MIN; current = 0; for (int i = n-1; i >= 0; --i) { current = max(a[i], current + a[i]); max_single = max(max_single, current); suffix_max[i] = max_single; } // 计算线性情况的最大值 int linear_max = INT_MIN; for (int i = 0; i < n-1; ++i) { linear_max = max(linear_max, prefix_max[i] + suffix_max[i+1]); } // 情况2:环形情况(总和减去最小子段和) int min_single = INT_MAX; vector<int> prefix_min(n), suffix_min(n); // 从左到右计算最小子段和 current = 0; for (int i = 0; i < n; ++i) { current = min(a[i], current + a[i]); min_single = min(min_single, current); prefix_min[i] = min_single; } // 从右到左计算最小子段和 min_single = INT_MAX; current = 0; for (int i = n-1; i >= 0; --i) { current = min(a[i], current + a[i]); min_single = min(min_single, current); suffix_min[i] = min_single; } // 计算环形情况的最大值 int circular_max = INT_MIN; for (int i = 0; i < n-1; ++i) { int sum = total - (prefix_min[i] + suffix_min[i+1]); circular_max = max(circular_max, sum); } // 处理全负数情况 if (max(circular_max, linear_max) < 0) { int max_val = *max_element(a.begin(), a.end()); return cout << max_val << endl; } // 返回较大值 cout << max(linear_max, circular_max) << endl; }
五、总结
该解法通过动态规划高效处理环形数组的最大子段和问题,关键在于对线性与环形情况的分解,以及巧妙利用“总和-最小子段和”转换环形问题。代码逻辑清晰,兼顾了边界处理,为同类环形DP问题提供了典型思路。
原创内容 转载请注明出处