`最大子段和，动态规划
设dp[i]表示结束位置为 i 的最大子段和，若子段可空，dp[i]=max(dp[i-1]+nums[i], 0)。
dp[i]只依赖dp[i-1]，降一维，将dp[i]记作currMax，有 pp p77 的如下算法。
currMax = 0, ans = INT_MIN
for (num : nums) {
currMax = max(currMax + num, 0)
ans = max(ans, currMax)
}
扩展：最大子段和，子段非空
dp[i] = max(dp[i-1]+nums[i], nums[i]) = nums[i] + max(dp[i-1], 0)
int maxSubArray(vector<int>& nums) {
int currMax = 0, ans = INT_MIN;
for (int num : nums) {
currMax = num + max(currMax, 0);
ans = max(ans, currMax);
}
return ans;
}
扩展：循环数组的最大子段和，子段非空
int maxSubarraySumCircular(vector<int>& A) {
// 1. 没跨越数组尾，= 最大子段和ansMax
// 2. 跨越数组尾，= arrSum - 最小子段和ansMin
// 特例：ansMax<0时，数组全是负数，arrSum==ansMin；要返回ansMax
int currMax = 0, ansMax = INT_MIN;
int currMin = 0, ansMin = INT_MAX;
int arrSum = 0;
for (int a : A) {
currMax = a + max(currMax, 0);
ansMax = max(ansMax, currMax);
currMin = a + min(currMin, 0);
ansMin = min(ansMin, currMin);
arrSum += a;
}
if (ansMax < 0) return ansMax;
return max(ansMax, arrSum - ansMin);
}
扩展：k 次重复数组的最大子段和
int kConcatenationMaxSum(vector<int>& arr, int k) {
// 最大子段和，如果arrSum<=0：
// 1. 在arr中间，k=1
// 2. 在两数组尾首，arr[suffix]+arr[prefix]，k=2
// 如果arrSum>0：
// 1. 在arr中间 + (k-1)*arrSum
// 2. 在两数组尾首，arr[suffix]+arr[prefix]+(k-2)*arrSum
// 总结：
// 对k<=2，照常找最大子段和；
// 对k>2且arrSum>0，再加上(k-2)*arrSum
long maxendinghere = 0, maxsofar = 0;
for (int i = 0; i < min(k, 2); i++) {
for (int a : arr) {
maxendinghere = max(maxendinghere + a, 0L);
maxsofar = max(maxsofar, maxendinghere);
}
}
const int MOD = 1e9 + 7;
long arrSum = accumulate(begin(arr), end(arr), 0);
if (k > 2 && arrSum > 0) {
return (maxsofar + (k - 2) * arrSum) % MOD;
}
return maxsofar % MOD;
}
扩展：最大子矩阵和
对 MxN 矩阵列举所有行区间 O(M^2)，对某个行区间将各行累加成一行，然后用最大子段和 O(N)算法求得该行区间的对应最大列区间。复杂度 O(M^2 * N)，见 ctci p614。
另：对于子区域和，如果先预处理得到{(0,0),(r,c)}区域的"累加和"数组sum[r,c]，那么区域和{(r1,c1), (r2,c2)}=sum[r2,c2]-sum[r2,c1-1]-sum[r1-1,c2]+sum[r1-1,c1-1]。而预处理时sum[r,c]=x[r][c]+sum[r-1,c]+sum[r,c-1]-sum[r-1,c-1]。整个算法 O(M^2 * N^2)。
联想：全是 1 的子矩阵
最大子段积
int maxProduct(vector<int>& nums) {
// 最大乘积可能来自负负得正，因此要保留最大乘积currMax和最小乘积currMin，
// 以nums[i]结尾子问题nums[0..i]的最大最小乘积来自 { currMax*nums[i], currMin*nums[i], nums[i] }
const int N = nums.size();
int currMax = 1, currMin = 1, ans = INT_MIN;
for (int num : nums) {
int cand1 = currMax * num, cand2 = currMin * num;
currMax = max({cand1, cand2, num});
currMin = min({cand1, cand2, num});
if (currMax > ans) ans = currMax;
}
return ans;
}
联想："全正数数组、子段积<K 的个数"参考 滑动数组解法
可有 1 个删除的最大子段和
int maximumSum(vector<int>& arr) {
// 设dp[i][0]表示以arr[i]结尾、子段中间没有删除过数的最大子段和，
// dp[i][1]表示以arr[i]结尾、子段中间删除过一个数的最大子段和。
// dp[i][0] = max(dp[i-1][0]+arr[i], arr[i])
// dp[i][1] = max(dp[i-1][0], dp[i-1][1]+arr[i])
// 第i项只依赖i-1项，省掉i这维，注意赋值顺序，
// dp[1] = max(dp[0], dp[1]+arr[i])
// dp[0] = max(dp[0]+arr[i], arr[i])
const int N = arr.size();
vector<int> dp({arr[0], 0}); // i==0
int ans = dp[0]; // 子段要非空
for (int i = 1; i < N; i++) {
dp[1] = max(dp[0], dp[1] + arr[i]);
dp[0] = max(dp[0] + arr[i], arr[i]);
ans = max({ans, dp[0], dp[1]});
}
return ans;
}
找数组中两个不相交的子段 A 和 B，使|sum(A)-sum(B)|最大
使|sum(A)-sum(B)|最大，从中间某点 i 把数组分成两半，就是找 max{ abs(左半最大子段和-右半最小子段和), abs(左半最小子段和-右半最大子段和) }，遍历分割点 i。