class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        size = len(nums)
        nsize = size - k + 1
        sums = [0] * nsize
        maxa = [0] * nsize
        maxb = [0] * nsize
        total = 0
        for x in range(size):
            total += nums[x]
            if x >= k - 1:
                sums[x - k + 1] = total
                total -= nums[x - k + 1]
        maxn, maxi = 0, 0
        for x in range(nsize):
            if sums[x] > maxn:
                maxn, maxi = sums[x], x
            maxa[x] = (maxn, maxi)
        maxn, maxi = 0, nsize - 1
        for x in range(nsize - 1, -1, -1):
            if sums[x] > maxn:
                maxn, maxi = sums[x], x
            maxb[x] = (maxn, maxi)
        ansn, ansi = 0, None
        for x in range(k, nsize - k):
            va, ia = maxa[x - k]
            vb, ib = maxb[x + k]
            if sums[x] + va + vb > ansn:
                ansn = sums[x] + va + vb
                ansi = [ia, x, ib]
        return ansi

"""

nums=[1,2,1,2,6,7,5,1]
sum1=[1,3,4,6,12,19,24,25]
sum2=[3,3,3,8,13,12,6]
在[k, nsize - k)范围内枚举中段子数组的起点x
则3段子数组和 = 中段+左侧最大+右侧最大


如果这题不是三个数组 而是尽可能多的数组
可以考虑用动态规划
sum[i]=max(num[i]+sum[i-k],sum[i-k+1],.......)
class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        n=len(nums)
        if n<3:
            return []
        sum1=[0 for i in range(n)]
        sum1[0]=nums[0]
        for i in range(1,n):
            sum1[i]=sum1[i-1]+nums[i]
        sum2=[0 for i in range(n-k+1)]
        sum2[0]=sum1[k-1]
        for j in range(1,n-k+1):
            sum2[j]=sum1[k+j-1]-sum1[j-1]
        index=-1
        for middle in range(k,len(sum2)-k):
            left_num=max(sum2[:middle-k+1])
            middle_num=sum2[middle]
            right_num=max(sum2[middle+k:])
            if left_num+middle_num+right_num>index:
                index=left_num+middle_num+right_num
                ans=[sum2[:middle-k+1].index(left_num),middle,sum2[middle+k:].index(right_num)+middle+k]
        return ans
"""
s = Solution()
nums=[1,2,1,2,6,7,5,1]
k=2
print(s.maxSumOfThreeSubarrays(nums,k))
