<p>Given an integer array <code>nums</code> and an integer <code>k</code>, find three non-overlapping subarrays of length <code>k</code> with maximum sum and return them.</p>

<p>Return the result as a list of indices representing the starting position of each interval (<strong>0-indexed</strong>). If there are multiple answers, return the lexicographically smallest one.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,2,6,7,5,1], k = 2
<strong>Output:</strong> [0,3,5]
<strong>Explanation:</strong> Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,2,1,2,1,2,1], k = 2
<strong>Output:</strong> [0,2,4]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;&nbsp;2<sup>16</sup></code></li>
	<li><code>1 &lt;= k &lt;= floor(nums.length / 3)</code></li>
</ul>

"""
We are thinking about the gaps between our k-subarrays (and minimizing them).

We can encode our state in the same way that we will return it. We can write some helper
to translate between the two.

Fix that some index i be the end of one of our subarrays.

dpx[i] := maximum x-subarray group ending at or before i 
        = max(dpx[i-1], calculate the best subarray ending at i)
        = max(dpx[i-1], subarray_sum(i-k+1, i) + dpx-1[i-k])

        # note for the max we need to do _better_ than the prior

0: dp0[i] := 0 for all values
1: find the maximum subarray. dp1[i] := the maximum 1-subarray ending at or before i
2: dp2[i-k] (where dp is the maximum 1-subarray).
3. dp2[i - 2*k]
"""

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        pfx = list(accumulate(nums))

        def subarraySum(startPos, endPos):
            if endPos >= len(nums):
                raise "subarraySum out of bounds"
            return pfx[endPos] if startPos == 0 \
                else pfx[endPos] - pfx[startPos - 1]
        def stateSum(subarrayStarts):
            if len(subarrayStarts) == 0 or -1 in subarrayStarts:
                return 0
            return sum(subarraySum(start, start + k - 1) for start in subarrayStarts)
        
        dp = [[[-1]*i for i in range(0, 4)] for _ in range(len(nums))]
        for i in range(len(nums)):
            if i >= k - 1:
                newSubarray = [i - k + 1]
                if i == k - 1 or stateSum(newSubarray) > stateSum(dp[i-1][1]):
                    dp[i][1] = newSubarray
                else:
                    dp[i][1] = dp[i-1][1]
            for subarrayCt in range(2, 4):
                if i < subarrayCt * k - 1:
                    continue
                beforeIndex = i - k
                newSubarray = dp[beforeIndex][subarrayCt - 1] + [i - k + 1]
                if i == 0 or stateSum(dp[i - 1][subarrayCt]) < stateSum(newSubarray):
                    dp[i][subarrayCt] = newSubarray
                else:
                    dp[i][subarrayCt] = dp[i-1][subarrayCt]
        return dp[len(nums)-1][3]
28200