leetcode 1423 最大点数

如果使用递归时间会超时。使用记忆化递归也会超时。

        # memo={}
        # def dfs(index,nums,sumval,i,j):

        #     if (i,j) in memo:
        #         return memo[(i,j)]

        #     if index==k:

        #         return sumval

        #     if i>j:

        #         return sumval

        #     left=dfs(index+1,nums[1:],sumval+nums[0],i+1,j)
        #     right=dfs(index+1,nums[:-1],sumval+nums[-1],i,j-1)

        #     maxvalue=max(left,right)

        #     memo[(i,j)]=maxvalue
        #     return maxvalue

        # return dfs(0,cardPoints,0,0,len(cardPoints)-1)          

通过滑动窗口，或者前缀和来解决
滑动窗口通过求中间连续数组和的最小值，进而寻求两侧k个数字的和最大值。

        # presum=0
        # res=float('inf')
        # for i in range(len(cardPoints)):
        #     presum+=cardPoints[i]
        #     if i>=len(cardPoints)-k:
        #         presum-=cardPoints[i-len(cardPoints)+k]
        #     if i>=len(cardPoints)-k-1:
        #         res=min(presum,res)

        # return sum(cardPoints)-res

也可以通过循环数组来进行求解，初始化指针为len-k，然后向前移动指针，范围是len-k,len+k,取数组中元素的时候需要取余。

        res=0
        sumval=0


        sumval=sum(cardPoints[-k:])
        res=max(res,sumval)

        for i in range(k):

            sumval+=cardPoints[i]
            sumval-=cardPoints[len(cardPoints)-k+i]
            res=max(res,sumval)

        return res

使用前缀和，通过记录所有元素之前的前缀和，通过作差的方式来得到连续数组的最小值，注意是最小值，然后通过所有元素的和减去连续元素的最小值来获得选择元素的最大值。

        presum=[0]*(len(cardPoints)+1)
        maxvalue=float('inf')
        for i in range(1,len(cardPoints)+1):
            presum[i]+=presum[i-1]+cardPoints[i-1]
        for i in range(len(cardPoints)-k,len(cardPoints)+1):
            maxvalue=min(presum[i]-presum[i-len(cardPoints)+k],maxvalue)

        return presum[len(cardPoints)]-maxvalue