您的位置:首页 > 健康 > 美食 > day-53 两个线段获得的最多奖品

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

2024/12/23 8:38:44 来源:https://blog.csdn.net/qq_53568730/article/details/142149642  浏览:    关键词: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){//长度超过kleft++;}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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com