难度: Medium
给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。
返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
由于 结果可能会很大，需要返回的 109 + 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 <= 1051 <= k <= 105-104 <= arr[i] <= 104运行时间: 58 ms
内存: 27.6 MB
"""
将问题划分成子数组是否包含整个 arr
-> 如果包含整个子数组，即sum(arr) > 0 ,答案变成 k-2 个 sum(arr) + arr*2 的最大子数组和
-> 如果不包含子数组，答案就是 arr*2 的最大子数组和 if k > 1 else arr 的最大子数组和
"""
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
M = 10**9 + 7
s, maxes = 0, 0
for a in arr * min(k, 2):
s = a if s < 0 else s + a
if s > maxes:
maxes = s
if k <= 2:
return maxes % M
return (max(sum(arr), 0) * (k-2) + maxes) % M
该题解利用了Kadane算法来找出最大的子数组和，同时考虑了数组被重复k次时的不同情况： 1. 当数组总和为正时，最大和可能包括中间多个完整的数组和两头的部分数组。这种情况下，计算方式为两个数组的最大子数组和加上中间k-2个数组的总和。 2. 当数组总和不为正时，最大子数组和只可能出现在前两个数组内，因为更多的重复只会增加非正的总和。 3. 当k小于或等于2时，不需要考虑多个数组的累加总和，只需计算前k个数组内的最大子数组和。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
M = 10**9 + 7 # 用来取模的数
s, maxes = 0, 0 # s是当前子数组的和，maxes是遇到的最大子数组和
# 遍历至多两倍数组长度以覆盖所有情况
for a in arr * min(k, 2):
s = a if s < 0 else s + a # Kadane算法核心：如果当前和小于0，则重新开始计数
if s > maxes:
maxes = s # 更新最大子数组和
# 如果k<=2，返回计算的最大子数组和；否则考虑中间k-2个完整数组的和
if k <= 2:
return maxes % M
return (max(sum(arr), 0) * (k-2) + maxes) % M # 计算包含中间数组的总和
当数组总和为正时，重复数组k次可以看作是提供了一个机会，使得通过选择多个完整的数组副本来增加总和成为可能。在这种情况下，最大子数组和可能由三部分组成：第一部分是从第一个数组中选择的最大子数组的结束部分；第二部分是中间的k-2个完整数组的总和；第三部分是从最后一个数组中选择的最大子数组的开始部分。这种组合可以实现当数组总和为正时的最大化收益，因为每增加一个完整的数组副本，总和都会增加。
通过遍历两倍数组长度，我们可以覆盖所有单个数组和两个连续数组组合的可能的最大子数组和情况。这是因为最大子数组可能起始于第一个数组末尾并结束在第二个数组开始，或者仅存在于一个数组内部。遍历超过两倍长度不会发现新的最大子数组情况，因为任何更长的重复只会是前两个数组模式的重复，特别是当数组总和为负或零时，更多的重复并不会产生更大的子数组和。
题解中的逻辑确实表明，当k > 2且数组总和为负或零时，最大子数组和不会超过两个数组长度内找到的最大子数组和。这是因为，如果整个数组的总和不为正，那么重复数组只会增加更多的非正总和，从而不可能通过添加更多的数组副本来增加最大的子数组和。因此，对于k > 2的情况，如果数组总和为负或零，我们只需考虑最初两个数组内的最大子数组和，再多的重复也不会提高这个值。
在计算机科学中，特别是在处理大数和避免整数溢出的算法问题时，常常使用取模操作来保持数值在一个安全的可管理的范围内。将结果模上一个大质数（如10^9 + 7）可以防止结果因为数值过大而溢出，同时也是许多编程比赛和在线判题系统的常见要求，以保证结果的一致性和比较。