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

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

贪心

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

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

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

maxSufmaxPre均可以通过遍历累加解决

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

\[tmpSub_i = \begin{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)

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

上一篇:idea中搭建完springboot项目后,上传到码云提示:Push rejected


下一篇:4月26日云栖精选夜读:数据中心散热,阿里居然玩出了这些花样