day-53 两个线段获得的最多奖品

思路
dp[right] 表示右端点不超过 prizePositions[right] 的线段可以覆盖最大奖品数量，然后枚举后面一条线段的右端点（第一条线段在第二条线段左边），第二条线段的长度可以表示为right-left+1;第一条线段的长度可以表示dp[left]

解题过程
通过枚举dp[left]+right-left+1的值，最大的那个即为答案

Code

class Solution {
    public int maximizeWin(int[] prizePositions, int k) {
        int len=prizePositions.length;
        int dp[]=new int[len+1];
        int left=0;
        int ans=0;
        for(int right=0;right<len;right++){
            while(prizePositions[right]-prizePositions[left]>k){//长度超过k
                left++;
            }
            ans=Math.max(ans,right-left+1+dp[left]);
            dp[right+1]=Math.max(dp[right],right-left+1);
        }
        return ans;
    }
}

作者：菜卷
链接：https://leetcode.cn/problems/maximize-win-from-two-segments/solutions/2913554/liang-ge-xian-duan-huo-de-de-zui-duo-jia-8mtm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

原文地址：https://blog.csdn.net/qq_53568730/article/details/142149642

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！