# In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.
#
# Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.
#
# Return the result as a list of indices representing the starting position of each interval (0-indexed). If there
# are multiple answers, return the lexicographically smallest one.
#
# Example:
# Input: [1,2,1,2,6,7,5,1], 2
# Output: [0, 3, 5]
# Explanation: 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.
# Note:
# nums.length will be between 1 and 20000.
# nums[i] will be between 1 and 65535.
# k will be between 1 and floor(nums.length / 3).


class Solution(object):
    # TLE, O(n^3)
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        l = len(nums)
        sums = [0] * (l + 1)

        # notice, sums[0] = 0
        # sums[1] = nums[0]
        # sums[2] = nums[0] + nums[1] etc.
        for n, v in enumerate(nums):
            sums[n + 1] = sums[n] + v

        maxSum, res = 0, []
        # print l, k
        # print l + 1 - 3 * k
        for i in xrange(1, l + 2 - 3 * k):  # bugfixed should be l+2 - 3*k, below also the same
            for j in xrange(i + k, l + 2 - 2 * k):
                for m in xrange(j + k, l + 2 - k):
                    # sums[i+k-1] - sums[i-1] first k sum
                    # sums[j+k-1] - sums[j-1] second k sum
                    # sums[m+k-1] - sums[m-1] second k sum
                    t = sums[i + k - 1] + sums[j + k - 1] + sums[m + k - 1] - sums[i - 1] - sums[j - 1] - sums[m - 1]
                    # print t, i, j, m
                    if t > maxSum:
                        # bugfixed i , j m is the index start from 1, so we need minus 1
                        res, maxSum = [i - 1, j - 1, m - 1], t

        return res

    def maxSumOfThreeSubarrays2(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        l = len(nums)
        sums, left, right = [0] * (l + 1), [0] * l, [0] * l

        # notice, sums[0] = 0
        # sums[1] = nums[0]
        # sums[2] = nums[0] + nums[1] etc.
        for n, v in enumerate(nums):
            sums[n + 1] = sums[n] + v

        # target is the intial value of left DP array, in fact sums[0] is 0, so target = sums[k]
        # left[k] = 1 not 0 because I count index on sums array, not nums
        target, left[k] = sums[k] - sums[0], 0

        for i in xrange(k, l):  # notice this range is the range of 'nums' array, not 'sums'
            # if k-sum is bigger, we record its starting position
            # notice , there is no `>=`, because we need lexicographically small
            if sums[i + 1] - sums[i + 1 - k] > target:
                target = sums[i + 1] - sums[i + 1 - k]
                left[i] = i - k + 1
            else:
                left[i] = left[i - 1]

        target, right[l - k] = sums[l] - sums[l - k], l - k

        for i in reversed(xrange(0, l - k)):
            # notice , there is  `=`, because we need lexicographically small, when we move from right to left
            # >= is necessary
            if sums[i + k] - sums[i] >= target:
                target = sums[i + k] - sums[i]
                right[i] = i
            else:
                right[i] = right[i + 1]

        # move the k eles in the middle, then add left max and right max to it
        maxSum, res = 0, []
        for i in xrange(k, l + 1 - 2 * k):
            mid, l, r = sums[i + k] - sums[i], left[i - 1], right[i + k]
            lefts = sums[l + k] - sums[l]
            rights = sums[r + k] - sums[r]
            if lefts + mid + rights > maxSum:
                maxSum = lefts + mid + rights
                res = [l, i, r]

        return res


if __name__ == '__main__':
    print Solution().maxSumOfThreeSubarrays2([1, 2, 1, 2, 6, 7, 5, 1], 2)
    print Solution().maxSumOfThreeSubarrays([1, 2, 1, 2, 6, 7, 5, 1], 2)
    print Solution().maxSumOfThreeSubarrays2([7, 13, 20, 19, 19, 2, 10, 1, 1, 19], 3)
    print Solution().maxSumOfThreeSubarrays([7, 13, 20, 19, 19, 2, 10, 1, 1, 19], 3)
