🧠 题解思路
这个问题是一个经典的 最大子段和问题（Maximum Subarray Sum）。
我们可以用 动态规划（DP） 或 Kadane算法 来解决：
- 设
dp[i]表示以第i个地段结尾的最大连续子段和。 - 转移方程为：
dp[i] = max(a[i], dp[i-1] + a[i])
- 其中：
a[i]表示第i个地段的能源值。- 如果前一段和为负数，那么从当前地段重新开始会更优。
最终答案为所有 dp[i] 中的最大值。
🧮 时间复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)（可以优化为仅用两个变量）
💻 C++参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int max_sum = a[0]; // 记录最大子段和
int curr_sum = a[0]; // 当前子段和
for (int i = 1; i < n; ++i) {
// 如果当前和为负，则重新开始
curr_sum = max(a[i], curr_sum + a[i]);
max_sum = max(max_sum, curr_sum);
}
cout << max_sum << "\n";
return 0;
}