<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]:
        
        
# three windows size==k:w1,w2,w3,can just keep 3 adjacent windows move.
# just like dp,since 3 is small, we can do it manually, update maxw1 if w1>maxw1=> update maxw2 if maxw1+w2>maxw2=>update maxw3 if maxw2+w3>maxw3

# it is a sliding window problems, but with three windows with the same size
class Solution(object):
    def maxSumOfThreeSubarrays(self,nums, k):
        w1, w2, w3 = sum(nums[:k]), sum(nums[k:2*k]), sum(nums[2*k:3*k])
        mw1, mw2, mw3 = w1, w1 + w2, w1 + w2 + w3 # max sum of 1 winds, 2 winds, 3 winds
        mw1index, mw2index, mw3index = [0], [0, k], [0, k, 2*k] # mw1, mw2, mw3's index.
        
        # move the last index
        # the max sum of the three non-overlapping subarray ended at index i
        # this is a DP problem indeed
        for i in range(1, len(nums) - 3*k + 1): #last index for w1 window will be n-3k
            # get new window sum
            w1 += nums[i - 1 + k] - nums[i - 1]
            w2 += nums[i - 1 + 2*k] - nums[i - 1 + k]
            w3 += nums[i - 1 + 3*k] - nums[i - 1 + 2*k]
            
            if w1 > mw1:
                mw1, mw1index = w1, [i]
            if mw1 + w2 > mw2: # before the third window, the max of the two sub arrays 
                # only when the first two windows sum larger the pervious two windows sum, then we update the second the window!!!
                # even thought the mw1 is updated, but the mw1 + w2 with the current second window <= the previous one, we do not update it
                # because the first two windows does not turn bigger
                mw2, mw2index = mw1 + w2, mw1index + [i + k]
            if mw2 + w3 > mw3: # before (include) the current index, the max of the three sub arrays 
                # only when the first three windows sum larger the pervious threes windows sum, then we update the second the window!!!
                mw3, mw3index = mw2 + w3, mw2index + [i + 2*k]
                
        return mw3index
    
    
"""
class Solution:
    def maxSumOfThreeSubarrays(self, nums, k):
        # Best single, double, and triple sequence found so far
        bestSeq = 0
        bestTwoSeq = [0, k]
        bestThreeSeq = [0, k, k*2]

        # Sums of each window
        seqSum = sum(nums[0:k])
        seqTwoSum = sum(nums[k:k*2])
        seqThreeSum = sum(nums[k*2:k*3])

        # Sums of combined best windows
        bestSeqSum = seqSum
        bestTwoSum = seqSum + seqTwoSum
        bestThreeSum = seqSum + seqTwoSum + seqThreeSum

        # Current window positions
        seqIndex = 1
        twoSeqIndex = k + 1
        threeSeqIndex = k*2 + 1
        
        while threeSeqIndex <= len(nums) - k:
            # Update the three sliding windows
            seqSum = seqSum - nums[seqIndex - 1] + nums[seqIndex + k - 1]
            seqTwoSum = seqTwoSum - nums[twoSeqIndex - 1] + nums[twoSeqIndex + k - 1]
            seqThreeSum = seqThreeSum - nums[threeSeqIndex - 1] + nums[threeSeqIndex + k - 1]
            
            # Update best single window
            if seqSum > bestSeqSum:
                bestSeq = seqIndex
                bestSeqSum = seqSum

            # Update best two windows
            if seqTwoSum + bestSeqSum > bestTwoSum:
                bestTwoSeq = [bestSeq, twoSeqIndex]
                bestTwoSum = seqTwoSum + bestSeqSum

            # Update best three windows
            if seqThreeSum + bestTwoSum > bestThreeSum:
                bestThreeSeq = bestTwoSeq + [threeSeqIndex]
                bestThreeSum = seqThreeSum + bestTwoSum

            # Update the current positions
            seqIndex += 1
            twoSeqIndex += 1
            threeSeqIndex += 1

        return bestThreeSeq
"""
19600