发表于 2024.07.05

• 结合多种情况的解法，涉及到最大前缀和、最大后缀和以及最大子数组和。由于数组允许重复k次，需要考虑前后拼接的情况。结果取自以下几种情况的最大值：

  1. (如果k > 2) 最大前缀和 + 最大后缀和 + (k - 2) * 数组和 – 第一个数组的最大后缀 + 中间的k - 2个数组 + 最后一个数组的最大前缀

  2. (如果k > 2) 最大前缀和 + 最大后缀和 – 即仅取跨越前后拼接的子数组, 如果数组总和为负数的话, 没必要在中间拼接

  3. 最大的子数组和 – 即有可能不是前缀也不是后缀，而是数组中间的某个子数组，不能拼接连续的数组

  4. 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，因此不会出现这种情况。那么会不会有仅有最大前缀的情况呢，答案是仅出现在最大前缀即为最大和子数组的情况下，要不然取后者会更优。

• LC 题目链接