Leetcode 1191. K-Concatenation Maximum Sum

Problem statement

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

Solution

We need to use Kadane here. If k == 1, just return answer for it. If k >= 2, we can have two options: either we have answer for arr + arr, or it is something like ...|...---|------|------|...|------|--....|...: in this case we have k - 2 times full sum and also suffix and prefix. These two cases can be written as one formula.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def kConcatenationMaxSum(self, arr, k):
        def maxSubArray(A):
            dp = [A[0]] + [0]*(len(A) - 1)
            for i in range(1, len(A)):
                dp[i] = max(A[i], A[i] + dp[i-1])
            return max(max(dp), 0)
        
        N = 10**9 + 7
        if k == 1: return maxSubArray(arr) % N
        return ((k-2) * max(sum(arr), 0) + maxSubArray(arr*2)) % N