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

"""
[1,2,1,2,6,7,5,1]
[1,2]
[2,1]
[1,2]
[2,6]
[6,7]
[7,5]
[5,1]

fwd_max[i] =  max window i and before.
back_max[i] = max window i and after.

"""

class Solution:
    def calc_fwd_max(self, nums, k, is_back):
        fwd_max = [-1] * len(nums)
        fwd_max_sum = [-1] * len(nums)
        s = 0
        for i in range(k-1):
            s += nums[i]
        cmax = -1
        max_pos = -1
        for i in range(k-1, len(nums)):
            s += nums[i]
            if i - k >= 0:
                s -= nums[i-k]
            if s > cmax or (is_back and s >= cmax):
                cmax = s
                max_pos = i - k + 1
            fwd_max[i] = max_pos
            fwd_max_sum[i] = cmax
        return (fwd_max, fwd_max_sum)


    """
      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
      ...... i
      fwd_max_sum[i] -> window ends at i]
      fwd_max[i]     -> where the max window begins

      for back we want:
        back_max_sum[i] -> window starts at [i
        back_max[i] -> where the max window begins
    """
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        # calc fwd_max.
        fwd_max, fwd_max_sum = self.calc_fwd_max(nums, k, False)
        back_max, back_max_sum = self.calc_fwd_max(nums[::-1], k, True)
        back_max_sum = back_max_sum[::-1]
        back_max = back_max[::-1]
        print(back_max_sum)
        print(back_max)
        print('----')
        for i in range(len(nums)):
            if back_max[i] != -1:
                back_max[i] = len(nums) - back_max[i] - k                
        
        # rolling window.
        s = 0
        for i in range(k-1):
            s += nums[i]
        ans_sum = -1
        ans = []
        print(back_max_sum)
        print(back_max)

        for i in range(k-1, len(nums)):
            s += nums[i]
            if i - k >= 0:
                s -= nums[i - k]
            # window is in positions [i-k+1, i]
            if i - k >= 0 and i + 1 < len(nums):
                total = fwd_max_sum[i - k] + s + back_max_sum[i + 1]
                if total > ans_sum:
                    ans_sum = total
                    ans = [fwd_max[i-k], i-k+1, back_max[i+1]]
        return ans

            

            



        
20600