# Time:  O(n)
# Space: O(n)

class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        n = len(nums)
        accu = [0]
        for num in nums:
            accu.append(accu[-1]+num)
       
        left_pos = [0] * n
        total = accu[k]-accu[0]
        for i in xrange(k, n):
            if accu[i+1] - accu[i+1-k] > total:
                left_pos[i] = i+1-k
                total = accu[i+1]-accu[i+1-k]
            else:
                left_pos[i] = left_pos[i-1]
        
        right_pos = [n-k] * n
        total = accu[n]-accu[n-k]
        for i in reversed(xrange(n-k)):
            if accu[i+k]-accu[i] > total:
                right_pos[i] = i;
                total = accu[i+k]-accu[i]
            else:
                right_pos[i] = right_pos[i+1]
        
        result, max_sum = [], 0
        for i in xrange(k, n-2*k+1):
            left, right = left_pos[i-1], right_pos[i+k]
            total = (accu[i+k]-accu[i]) + \
                    (accu[left+k]-accu[left]) + \
                    (accu[right+k]-accu[right])
            if total > max_sum:
                max_sum = total
                result = [left, i, right]
        return result

@@ -22,16 +22,799 @@
 : O(n)%0A%0A
+# In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.%0A#%0A# Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.%0A#%0A# Return the result as a list of indices representing the starting position of each interval (0-indexed).%0A# If there are multiple answers, return the lexicographically smallest one.%0A#%0A# Example:%0A# Input: %5B1,2,1,2,6,7,5,1%5D, 2%0A# Output: %5B0, 3, 5%5D%0A #   %0A# Explanation: Subarrays %5B1, 2%5D, %5B2, 6%5D, %5B7, 5%5D correspond to the starting indices %5B0, 3, 5%5D.%0A# We could have also taken %5B2, 1%5D, but an answer of %5B1, 3, 5%5D would be lexicographically larger.%0A#%0A# Note:%0A# - nums.length will be between 1 and 20000.%0A# - nums%5Bi%5D will be between 1 and 65535.%0A# - k will be between 1 and floor(nums.length / 3).%0A%0A
 class So

Update maximum-sum-of-3-non-overlapping-subarrays.py