1191.md

1191. K-Concatenation Maximum Sum

Solution 1 (time O(n), space O(n))

class Solution(object):
    def kConcatenationMaxSum(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        mod = 10 ** 9 + 7
        n = len(arr)
        ans = 0
        dp = [0 for _ in range(n)]
        dp[0] = arr[0]
        for i in range(1, n):
            dp[i] = max(dp[i - 1] + arr[i], arr[i])
        ans = max(ans, max(dp)) % mod
        if k > 1:
            dp1 = [0 for _ in range(n)]
            dp1[0] = arr[0]
            for i in range(1, n):
                dp1[i] = dp1[i - 1] + arr[i]
            dp2 = [0 for _ in range(n)]
            dp2[n - 1] = arr[n - 1]
            for i in range(n - 2, -1, -1):
                dp2[i] = dp2[i + 1] + arr[i]
            arr_sum = sum(arr)
            if arr_sum < 0:
                ans = max(ans, max(dp1) + max(dp2)) % mod
            else:
                ans = max(ans, max(dp1) + max(dp2) + arr_sum * (k - 2)) % mod
        return ans