My Python DP solution


  • 0
    C

    the state-transit equation
    f[i][j]=max(f[i-1][x])+sum(a[j-k+1,j]) 0<x<=j-k and j>=k

    import copy
    class Solution(object):
        def maxSumOfThreeSubarrays(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            s=0
            n=len(nums)
            ksum=[0 for i in range(n)]
            for i in range(n):
                s+=nums[i]
                #print s
                if i < k-1: continue
                else:
                    ksum[i]=s
                    s-=nums[i-k+1]
            f=[[0 for i in range(n)]for j in range(4)]
            f2=[[[0 for l in range(3)] for i in range(n)]for j in range(4)]
            for i in range(0,3):
                if i==0:
                    for j in range(k-1,n):
                        if ksum[j]>f[0][j-1]:
                            f[0][j]=ksum[j]
                            f2[0][j][0]=j-k+1
                        else:
                            f[0][j]=f[0][j-1]
                            f2[0][j][0]=f2[0][j-1][0]
                else:
                    for j in range(k,n):
                        if f[i-1][j-k]+ksum[j]>f[i][j-1]:
                            f[i][j]=f[i-1][j-k]+ksum[j]
                            f2[i][j]=copy.copy(f2[i-1][j-k])
                            f2[i][j][i] = j-k+1
                        else:
                            f[i][j]=f[i][j-1]
                            f2[i][j] = copy.copy(f2[i][j - 1])
    
                #print f[i]
                #print f2[i]
    
            return f2[2][n-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.