LeetCode 1191 K 次串联后最大子数组之和

LeetCode 1191 K 次串联后最大子数组之和

贪心

为了方便说明, 定义几个变量。对每个数组arr而言:

maxSub: 最大子数组之和
maxSuf: 最大后缀数组之和
maxPre: 最大前缀数组之和

[opt = egin{cases} maxSub &k=1 \ max(maxSuf + s_{arr}*(k-2) + maxPre, maxSub) &k>=2 end{cases} \ s_{arr} = max(0, sum(arr)) ]

maxSuf与maxPre均可以通过遍历累加解决

maxSub也是通过遍历选取, 不同在于每次都需要贪心选择局部最大值

[tmpSub_i = egin{cases} max(0, arr_i) &i=0 \ max(0, arr_i, tmpSub_{i-1} + arr_i) &i>=1 end{cases} \ i in [0, len(arr)) \ maxSub = max(tmpSub_i) ]

伪代码如下：

maxSub, tmpSub = 0, 0
for i, v in arr:
    tmpSub = max(0, v, tmpSub + v)
    maxSub = max(maxSub, tmpSub)

Python3

from typing import List

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        maxSub, tmpSub = 0, 0
        maxSuf, tmpSuf = 0, 0
        maxPre, s = 0, 0
        for i, v in enumerate(arr):
            tmpSub = max(0, v, tmpSub + v)
            maxSub = max(maxSub, tmpSub)

            tmpSuf += arr[-1 - i]
            maxSuf = max(maxSuf, tmpSuf)

            s += v
            maxPre = max(maxPre, s)
        if k <= 1:
            return maxSub
        s = max(0, s)

        opt = maxSuf + s * (k-2) + maxPre
        return max(opt, maxSub) % (10**9 + 7)