Leetcode 1299 Solution

This article provides solution to leetcode question 1299 (k-concatenation-maximum-sum)

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)