11 Max sum of 3 subarray

找sum最大，每个长度都是k 的三个subarray。 三个subarray不能有overlap。 举个栗子

nums = [1,2,1,2,6,7,5,1] 
k = 2

这个里面找到的就应该是

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

同样返回和。楼猪这题傻逼的写了个 N^3的解法。铁定跪了。回学校问了下大神，大神说dp， 我也明白dp怎么写了，O(N)。.

思路:这道题dp的公式是 dp[i] = Math.max(dp[i-1], dp[i-k] + sum(nums[i-k:i])）这里需要注意的是如果dp[i-k]已经有3个subarray了，那么我们用sum(nums[i-k:i])去尝试替换掉最小的一个。 因为k是常数，所以最后的复杂度是O（kn）就是O（n）

class Solution(object):
    def largestSubSum(self, nums, k):
        """
        :type nums: List[int]
        :rtype: int
        """

        # init DP store sum of pair in dp
        dp = [[] for _ in range(len(nums)+1)]
        print dp

        for i in range(2, len(nums)+1):
            # get sum of last 2 nums
            tmp = sum(nums[i-2:i])

            # if last length dp has less than 3 subarry add more
            if len(dp[i-k])<=2:
                cur = dp[i-k] + [tmp]
            else: # else replace the smallest one if possible
                if dp[i-k]:
                    dp[i-k].sort()
                cur = dp[i-k][1:] + [max(tmp, dp[i-k][0])]

            # compare the 
            if dp[i-1] and sum(dp[i-1])>sum(cur):
                dp[i] =  dp[i-1]
            else:
                dp[i] = cur

            print dp
        return sum(dp[-1])


nums = [1,2,1,2,6,7,5,1]
so = Solution()
ans = so.largestSubSum(nums, 2)
print ans
# if we print dp array 
#[[], [], [3], [3], [3, 3], [3, 8], [3, 3, 13], [3, 8, 12], [3, 8, 12]]