首页 > 其他分享 >【LeetCode】1798. 你能构造出连续值的最大数目

【LeetCode】1798. 你能构造出连续值的最大数目

时间:2023-02-04 11:12:53浏览次数:65  
标签:1798 硬币 最大值 coins 构造 数目 LeetCode

1798. 你能构造出连续值的最大数目

题目链接:1798. 你能构造出连续值的最大数目

本题使用动态规划。

首先将coins按照从小到大排序。

假设前n个硬币能够构造出来连续值的最大值(最大数目-1,因为最大数目包括0)为m。

我们现在的问题就是,加上第n+1个硬币,能否构造出m+1(因为数字越来越大,如果第n+1个硬币都无法构造出m+1,那加上更大的更不可能构造出m+1了)。

由于前面n个硬币能构造出0~m,所以前面的n个硬币可以构造出一个数k(0<=k<=m),加入存在k,使得k+coins[n+1]=m+1,那么前n+1个硬币就能构造出m+1,可得1<=coins[n+1]<=m+1,左边的条件必成立,所以我们只要判断右边的条件就能知道是否能构成m+1。

但是构造出m+1是不够的,因为题目要的是“最大”,和构造m+1的步骤同理,我们可以用k+coins[n+1]=m+i来构造后续的数字,我们的目标是让m+i最大,所以要让k取最大值,易知,可以构造出的最大的数就是m+coins[n+1]

综上,如果前n个数能构造出连续值的最大值为m,当第n+1个数小于等于m+1时,前n+1个数能构造出连续值的最大值为m+coins[n+1]

代码如下:

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        maxV = 0
        coins.sort()
        for c in coins:
            if c <= maxV + 1:
                maxV += c
            else:
                return maxV + 1
        return maxV + 1

标签:1798,硬币,最大值,coins,构造,数目,LeetCode
From: https://www.cnblogs.com/yangxuanzhi/p/17091092.html

相关文章