<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>

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
# similar: 121, 122, 123**, 188**, 53, 309**, 714, 689

                                        
 # best/easit: sol2: dp: Will be make a difference if the question generalize from 3 subarray to n subarray
# similar to buy and sell stock 
        p = [0] # pre-fixed sum
        for i in nums: p.append(p[-1]+i)           
        dp = [0]*len(p)
        ans = [[] for _ in range(len(p))]
        for _ in range(3): # can generarlized to n
                dp2 = [0]*len(p)
                ans2 = [[] for _ in range(len(p))]
                for i in range(1, len(p)):
                        if i-k>=0 and dp[i-k] + p[i]-p[i-k] > dp2[i-1]:
                                dp2[i] = dp[i-k] + p[i]-p[i-k]
                                ans2[i]= ans[i-k] + [i-k]
                        else:
                                dp2[i] = dp2[i-1]
                                ans2[i] = ans2[i-1]
                dp, ans = dp2.copy(), ans2.copy()
        return ans[-1]                        
                        
        
        
        
 # sol1: best, use prefix sum to translate into buy and sell stock. Linear time/space
 # consider the answer of i1, i2, i3. dp[j][i] denotes the maximum profit from 0 to i for j transactions. dp[j][i] = max(dp[j][i-1], dp[j-1][i-k] + p[i]-p[i-k]) where 0<=j<=3, 0<=i<=len(p)-1
        p = [0] # price
        for i in nums: p.append(p[-1]+i)              
        dp = [[0]*len(p) for _ in range(4)]
        ans = [[[] for _ in range(len(p))] for _ in range(4)]
        for j in range(1, 4):
                for i in range(1, len(p)):
                        if i-k>=0 and dp[j-1][i-k] + p[i]-p[i-k] > dp[j][i-1]:
                                dp[j][i] = dp[j-1][i-k] + p[i]-p[i-k]
                                ans[j][i]= ans[j-1][i-k] + [i-k]
                        else:
                                dp[j][i] = dp[j][i-1]
                                ans[j][i] = ans[j][i-1]
        return ans[-1][-1]
                        

25100