| 题目链接 | 1191. K 次串联后最大子数组之和 |
|---|---|
| 思路 | 前缀和/动态规划-最大子数组和-简单变体 |
| 题解链接 | dp做法正确性的详细证明（图帮助理解） |
| 关键点 | 分情况讨论（\(k\ge2\)）：1. 序列和小于0 2. 序列和大于等于0 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
MOD = 10 ** 9 + 7
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
answer = 0
dp = 0
for num in nums:
dp = max(dp, 0) + num
answer = max(answer, dp)
answer %= MOD
return answer
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
if k == 1:
return self.maxSubArray(arr)
sum_ = sum(arr)
if sum_ < 0:
return self.maxSubArray(arr + arr)
else:
return (self.maxSubArray(arr + arr) + (k-2) * sum_) % MOD