本文涉及的知识点

C++前后缀分解

LeetCode1191. K 次串联后最大子数组之和

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。
返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，需要返回的 10⁹ + 7 的 模 。
示例 1：
输入：arr = [1,2], k = 3
输出：9
示例 2：
输入：arr = [1,-2,1], k = 5
输出：2
示例 3：
输入：arr = [-1,-2], k = 7
输出：0
提示：
1 <= arr.length <= 10⁵
1 <= k <= 10⁵
-10⁴ <= arr[i] <= 10⁴

前后缀分解 最大子段和

n = num.size
x1 = $\sum$num
pre[i]是num长度小于等于i的前缀和的最小值。i$\in$[0,n]。
suff[i]是num长度小于等于i的后缀和的最小值。i$\in$[0,n]。
一，只用到了一个num。
for i = 0 To n
最大值(x1-pre[i]-suf[n-i])
二，用到了2个num,必须k >=2。
答案是x2= x1-pre.back()+ x1 - suff.back() 整数范围。
三，用到了2个以上num。
如果 k > 2 ,x1>0。加上x1$\times$(k-2)。已经超过int32范围。

代码

核心代码

class Solution {
		public:
			int kConcatenationMaxSum(vector<int>& arr, int k) {
				const int N = arr.size();
				auto Pre = [&](const vector<int>& arr) {
					vector<int> ret(1);
					int sum = 0;
					for (const auto& i : arr) {
						sum += i;
						ret.emplace_back(min(sum,ret.back()));
					}
					return ret;
				};
				auto pre = Pre(arr);
				auto suff = Pre(vector<int>(arr.rbegin(), arr.rend()));
				const long long sum = accumulate(arr.rbegin(), arr.rend(), 0);
				long long ans = 0;
				for (int i = 0; i <= N; i++) {
					ans = max(ans,sum - pre[i] - suff[N-i] );					
				}
				if (k < 2) { return ans; }
				ans = max(ans, sum - pre.back() + sum - suff.back());
				ans = max(ans, sum - pre.back() + sum - suff.back() + sum*(k-2));
				return ans % ((long long)1e9 + 7);
			}
		};

单元测试

vector<int> arr;
		int k;
		TEST_METHOD(TestMethod11)
		{
			arr = { 1, 2 }, k = 3;
			auto res = Solution().kConcatenationMaxSum(arr, k);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod12)
		{
			arr = { 1,-2,1 }, k = 5;
			auto res = Solution().kConcatenationMaxSum(arr, k);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			arr = { -1,-2 }, k = 7;
			auto res = Solution().kConcatenationMaxSum(arr, k);
			AssertEx(0, res);
		}