一、最大子数组和
题目要求找到数组中连续子数组的最大和,子数组需连续且至少包含一个元素。核心思路是拆解为:以第 i 个元素结尾的最大子数组和,要么是将第 i 个元素加入前一个子数组,要么是从第 i 个元素重新开始。

我们定义 dp[i] 表示以第 i 个元素为结尾的连续子数组的最大和。状态转移方程为 dp[i] = max(dp[i-1] + nums[i], nums[i])。如果 dp[i-1] + nums[i] 更大,说明延续之前的子数组更优;反之则从当前元素重新开始。初始化时 dp[0] = nums[0],遍历时维护一个变量记录全局最大值即可。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
int ret = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ret = max(ret, dp[i]);
}
return ret;
}
};
二、环形子数组的最大和
对于环形数组,最大子数组可能不跨首尾(普通情况),也可能跨越首尾(环形情况)。跨越首尾的情况等价于总和减去中间某段最小子数组的和。

我们需要同时计算非环形的最大子数组和 fmax,以及最小子数组和 gmin。若所有元素均为负数,直接返回 fmax;否则比较 与 取较大值。








