JZX轻语：简
LeetCode 1191 - K次串联后最大子数组之和
发表于2024年07月05日
结合多种情况的解法，涉及到最大前缀和、最大后缀和以及最大子数组和。由于数组允许重复k次，需要考虑前后拼接的情况。结果取自以下几种情况的最大值：
(如果
k > 2)最大前缀和 + 最大后缀和 + (k - 2) * 数组和– 第一个数组的最大后缀 + 中间的k - 2个数组 + 最后一个数组的最大前缀(如果
k > 2)最大前缀和 + 最大后缀和– 即仅取跨越前后拼接的子数组, 如果数组总和为负数的话, 没必要在中间拼接最大的子数组和 – 即有可能不是前缀也不是后缀，而是数组中间的某个子数组，不能拼接连续的数组
0 – 子数组为空
上述的四种情况可覆盖所有的最优解情况，因此只需要比较这四种情况的最大值即可。我们可以通过反证法证明正确性：
如果更优解期间跨越了至少一个完整的数组：
如果前面是最大后缀，后面是最大前缀，但中间没有拼接
k - 2个数组，那么如果数组总和为正数，可以继续拼接，得到更大的解；如果为负数，则去掉中间完整的数组，得到更大的解。如果前面并非最大后缀，则使用最大后缀，得到更大的解。
同理，如果后面并非最大前缀，则使用最大前缀，得到更大的解。
如果更优解没有跨越完整的数组：如果前面并非最大后缀，则使用最大后缀，得到更大的解；如果后面并非最大前缀，则使用最大前缀，得到更大的解。
如果该解为数组自身，则同时最大的子数组和亦是数组自身总和，因此不会有更优解。
class Solution:
MOD = 10 ** 9 + 7
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
pre_max_sum = arr_sum = 0
max_sub_arr_sum = 0
dp = 0
for i, num in enumerate(arr):
# 累加数组总和
arr_sum += num
# 更新最大和前缀
pre_max_sum = max(pre_max_sum, arr_sum)
# 更新最大和子数组
dp = max(dp + num, num)
max_sub_arr_sum = max(dp, max_sub_arr_sum)
# 最大和后缀即最后一个元素结尾的最大和子数组
suf_max_sum = dp
return max(
pre_max_sum + suf_max_sum + max(0, (k - 2) * arr_sum) if k > 1 else 0,
max_sub_arr_sum,
0
) % self.MOD由于上述解法不考虑空后缀的情况，会不会出现(k - 2)个数组 + 最后一个数组的最大前缀的情况呢？并非如此，如果后缀为空，意味着整个数组的总和为负数(如果总和为正数，则最大后缀直接取整个数组，矛盾)，那么(k - 2)个数组必然也小于0，因此不会出现这种情况。那么会不会有仅有最大前缀的情况呢，答案是仅出现在最大前缀即为最大和子数组的情况下，要不然取后者会更优。