53. 最大子数组和
https://leetcode.cn/problems/maximum-subarray/description/
给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
- 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，输出：6，解释：连续子数组[4,-1,2,1]的和最大，为6。
- 输入：nums = [1]，输出：1。
- 输入：nums = [5,4,-1,7,8]，输出：23。
提示：1 <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4。
我们用动态规划的思想来解决这个问题。
确定状态表示：根据经验和题目要求，我们用dp[i]表示：以i位置为结尾的子数组中的最大和。比如，dp[3]就表示：下标范围是[0, 3]，[1, 3]，[2, 3]，[3, 3]这4个子数组中的最大和。
推导状态转移方程：考虑dp[i]，
- 如果子数组的长度是1，只有下标范围是[i, i]的子数组符合条件，此时的子数组和是nums[i]。
- 如果子数组的长度大于1，那么以i位置为结尾的子数组中的最大和，就等于以i - 1位置为结尾的子数组中的最大和加上nums[i]，即dp[i - 1] + nums[i]。
dp[i]取上面2种情况的较大值，即dp[i] = max(nums[i], dp[i - 1] + nums[i])。
初始化：根据状态转移方程，我们需要初始化dp[0]的值。本题中，既可以根据状态表示直接初始化dp[0] = nums[0]；也可以在最前面加上一个辅助结点dp[0] = 0，这样max(num[0], dp[0] + nums[0]) = max(nums[0], 0 + nums[0]) = nums[0]，和前一种初始化方式等价。这里我们选择后一种方式。
填表顺序：根据状态转移方程，dp[i]依赖于dp[i - 1]，所以应从左往右填表。
返回值：由于我们并不确定子数组的结尾是那个位置，根据状态表示，我们应返回整个dp表除了辅助结点之外的最大值。
细节问题：假设nums有n个元素。由于新增了一个辅助结点，所以dp表的规模是1 x (n + 1)，且下标的映射关系为：dp[i]对应nums[i - 1]。
时间复杂度：O(N)，空间复杂度：O(N)。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
// 创建dp表
vector<int> dp(n + 1);
// 填表
for (int i = 1; i <= n; i++) {
dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
}
// 返回结果
return *max_element(dp.begin() + 1, dp.end());
}
};918. 环形子数组的最大和https://leetcode.cn/problems/maximum-sum-circular-subarray/description/给定一个长度为n的环形整数数组nums，返回nums的非空子数组的最大可能和。环形数组意味着数组的末端将会与开头相连呈环状。形式上，nums[i]的下一个元素是nums[(i + 1) % n]，nums[i]的前一个元素是nums[(i - 1 + n) % n]。子数组最多只能包含固定缓冲区nums中的每个元素一次。形式上，对于子数组nums[i]，nums[i + 1]，……，nums[j]，不存在i <= k1，k2 <= j其中k1 % n == k2 % n。
- 输入：nums = [1,-2,3,-2]，输出：3，解释：从子数组[3]得到最大和3。
- 输入：nums = [5,-3,5]，输出：10，解释：从子数组[5,5]得到最大和5 + 5 = 10。
- 输入：nums = [3,-2,2,-3]，输出：3，解释：从子数组[3]和[3,-2,2]都可以得到最大和3。
提示：n == nums.length，1 <= n <= 3 * 10^4，-3 * 10^4 <= nums[i] <= 3 * 10^4。
环形子数组分为2种情况：
- 环形子数组不包含首尾相连的部分，也就是说，环形子数组整体位于数组的中央。此时的最大和就是上题中的最大子数组和。
- 环形子数组包含首尾相连的部分，也就是说，环形子数组位于数组的左右两端。此时的最大和等于整个数组的和减去最小子数组和，最小子数组和的求法和上题中的最大子数组和完全类似。
也就是说，只需要求出最大子数组和fmax、最小子数组和gmin以及整个数组的和sum，本题的答案就是max(fmax, sum - gmin)。
其中，最小子数组和的求法也是按照上题中动态规划的思路，只需要把状态转移方程中的max改为min，返回结果也从返回最大值改为返回最小值。
这里需要注意一个细节问题，如果最终算出来的最小子数组和gmin，整个数组的和sum，满足gmin = sum，此时的sum - gmin = 0，并不表示包含首尾相连部分的环形子数组的最小和是0，因为此时gmin = sum说明最小子数组和是所有元素的和，那么从整个数组中去掉最小子数组和包含的元素后，就啥也不剩了，但是环形子数组中至少包含1个元素，所以这种情况要单独处理一下，如果算出来sum = gmin，那么最终结果就不是max(fmax, sum - gmin)，而是直接返回fmax。
我们可以用accumulate、max_element和min_element分别完成求和、求最大值、求最小值的操作，也可以在一个循环内手动完成。这里我们选择在一个循环内同时填2个表、求最大值、求最小值以及求和。其中，f表用来求最大子数组和，g表用来求最小子数组和。
时间复杂度：O(N)，空间复杂度：O(N)。
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size(), sum = 0, fmax = INT_MIN, gmin = INT_MAX;
// 创建dp表
vector<int> f(n + 1);
auto g = f;
// 填表
for (int i = 1; i <= n; i++) {
int x = nums[i - 1];
f[i] = max(x, f[i - 1] + x);
g[i] = min(x, g[i - 1] + x);
fmax = max(fmax, f[i]);
gmin = min(gmin, g[i]);
sum += x;
}
// 返回结果
return gmin == sum ? fmax : max(fmax, sum - gmin);
}
};
