【Leetcode Daily】1191K次串联后最大子数组之和

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个数组和一个数字k，这个数组将自我复制 k 次串联一起，求串联后的数组中子数组之和的最大值。（可以为空）

思路分享

• 当 k 为 1 时，就相当于只求这个数组的最大子数组和，与 【Leetcode Daily】53最大子数组和 无异；当 k 为 2 时，除了数组变化，与 1 没什么区别；当 k 大于等于 3，如果子数组从第一个到最后一个，那么就相当于在 k = 2 的基础上，加上了 k-2 个数组的总和。

  https://leetcode.cn/problems/k-concatenation-maximum-sum/solutions/3675237/fu-yong-53-ti-dai-ma-jian-ji-xie-fa-pyth-qmtp/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def maxSubArr(self, arr: List[int]):
        s = f = 0
        for i, x in enumerate(arr):
            f = max(f, 0) + x
            s = max(s, f)
            # print("%d %d" % (f, s))
        return s 

    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if k == 1:
            return self.maxSubArr(arr)
        s = self.maxSubArr(arr+arr)
        return (s + max(sum(arr)*(k-2), 0))% 1_000_000_007