1191-k-concatenation-maximum-sum.md

1191. K-Concatenation Maximum Sum - K 次串联后最大子数组之和

给你一个整数数组 arr 和一个整数 k。

首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。

举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。

然后，请你返回修改后的数组中的最大的子数组之和。

注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，所以需要 模（mod） 10^9 + 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 <= 10^5
• 1 <= k <= 10^5
• -10^4 <= arr[i] <= 10^4

---

题目标签：Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
python3	380 ms	27.2 MB

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        s = sum(arr)
        if s > 0:
            t = 0
            m1 = -1e20
            for a in arr:
                t += a
                m1 = t if t > m1 else m1
            t = 0
            m2 = -1e20
            for a in arr[::-1]:
                t += a
                m2 = t if t > m2 else m2
            if k > 1:
                return (m1 + m2 + s * (k - 2)) % 1000000007
            else:
                t = 0
                l = len(arr)
                r = -1e20
                for i in range(l):
                    if i == 0:
                        t = arr[i]
                    else:
                        if t > 0:
                            t = t + arr[i]
                        else:
                            t = arr[i]
                    r = max(r, t)
                return r % 1000000007
        elif s < 0:
            t = 0
            l = len(arr)
            r = -1e20
            for i in range(2 * l):
                if i == 0:
                    t = arr[i]
                else:
                    if t > 0:
                        t = t + arr[i % l]
                    else:
                        t = arr[i % l]
                r = max(r, t)
            return max(0, r)
        else:
            t = 0
            mi = 1e20
            ma = -1e20
            for a in arr:
                t += a
                mi = t if t < mi else mi
                ma = t if t > ma else ma
            return (ma - mi) % 1000000007