BinarySearch 0482 Largest K Sublist Sum

Problem statement

https://binarysearch.com/problems/Largest-K-Sublist-Sum/

Solution

Equal to Leetcode 1191. K-Concatenation Maximum Sum.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A, 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)
        
        if not A or not k: return 0
        if k == 1: return maxSubArray(A)
        return ((k-2) * max(sum(A), 0) + maxSubArray(A*2))