Problem statement

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/

Solution 1

Simpler version of Leetcode 0689 Maximum Sum of 3 Non-Overlapping Subarrays, here we do not need to reconstruct the answer. Also here we can have negative numbers here, so we need to define dp initial elements as -inf except the first line.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        m, n = 3, len(nums)
        dp = [[-float("inf")]*(n+1) for _ in range(m+1)] 
        for i in range(n+1): dp[0][i] = 0
        
        acc = [0] + list(accumulate(nums))
        windows = [acc[i+k] - acc[i] for i in range(n-k+1)] 

        for i in range(1, m + 1):
            for j in range(k - 1, n):
                dp[i][j + 1] = max(dp[i][j], windows[j+1-k] + dp[i-1][j-k+1])
        
        return dp[-1][-1]

Solution 2

We can use cumulative max of prefixes and suffixes.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        acc = [0] + list(accumulate(nums))
        Q = [acc[i] - acc[i-k] for i in range(k, n + 1)]
        pref = list(accumulate(Q, max))
        suff = list(accumulate(Q[::-1], max))[::-1]
        return max([pref[i-k] + Q[i] + suff[i+k] for i in range(k, n - 2*k + 1)])