Leetcode 1299 Solution

This article provides solution to leetcode question 1299 (k-concatenation-maximum-sum)
Categories:
Tags:
Access this page by simply typing in "lcs 1299" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/k-concatenation-maximum-sum

Solution

class Solution:
    def get_opt_from_left(self, arr):
        opt = 0
        s = 0

        for v in arr:
            s = (s + v)
            opt = max(s, opt) % 1000000007
        return opt

    def get_opt(self, arr, repeat=1):
        global_opt = 0
        local_opt = 0

        for i in range(repeat):
            for v in arr:
                local_opt = max(local_opt + v, v)
                global_opt = max(local_opt, global_opt) % 1000000007

        return global_opt


    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if k == 1:
            return self.get_opt(arr)

        s = sum(arr)

        if s >= 0:
            left_opt = self.get_opt_from_left(reversed(arr))
            right_opt = self.get_opt_from_left(arr)
            return (left_opt + right_opt + (k - 2) * s) % 1000000007
        else:
            return self.get_opt(arr, 2)