What is the key pattern in Maximum Number of Consecutive Values You Can Make?

The core pattern is a greedy choice plus invariant validation: if all values up to x are formable, adding coin v extends the range to x+v.

Why do we sort the coins before processing?

Sorting ensures we always add the smallest available coin to extend consecutive sums without skipping values, maintaining the invariant.

Can we use dynamic programming instead of greedy?

Dynamic programming works but is unnecessary; it increases time and space complexity while the greedy invariant directly computes the answer.

How do duplicates affect the solution?

Duplicates naturally extend the consecutive range. Each coin is considered in order, so repeated values simply add to maxConsecutive when applicable.

What happens if a coin value is larger than maxConsecutive+1?

A gap is created, and the consecutive sequence stops. No further consecutive sums can be formed from this point without smaller coins.

#1798

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以构造出 x 。请返回从 0 开始（包括 0 ），你最多能构造出多少个连续整数。你可能有多个相同值的硬币。…

数组贪心排序

题目描述

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以构造出 x 。

请返回从 0 开始（包括 0 ），你最多能构造出多少个连续整数。

你可能有多个相同值的硬币。

示例 1：

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
从 0 开始，你可以构造出 2 个连续整数。

示例 2：

输入：coins = [1,1,1,4]
输出：8
解释：你可以得到以下这些值：
- 0：什么都不取 []
- 1：取 [1]
- 2：取 [1,1]
- 3：取 [1,1,1]
- 4：取 [4]
- 5：取 [4,1]
- 6：取 [4,1,1]
- 7：取 [4,1,1,1]
从 0 开始，你可以构造出 8 个连续整数。

示例 3：

输入：nums = [1,4,10,3,1]
输出：20

提示：

coins.length == n
1 <= n <= 4 * 10⁴
1 <= coins[i] <= 4 * 10⁴

lightbulb

解题思路

方法一：排序 + 贪心

我们先对数组进行排序。然后定义 $ans$ 表示当前能够构造的连续整数的个数，初始化为 $1$ 。

遍历数组，对于当前遍历到的元素 $v$ ，如果 $v \gt ans$ ，说明无法构造出 $ans+1$ 个连续的整数，因此直接跳出循环，返回 $ans$ 即可。否则，说明可以构造出 $ans+v$ 个连续的整数，因此更新 $ans$ 为 $ans+v$ 。

最后返回 $ans$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        ans = 1
        for v in sorted(coins):
            if v > ans:
                break
            ans += v
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate recognizes that sorting is necessary for the greedy invariant to work.
question_mark
Candidate tracks the running maximum of consecutive values and correctly applies the extension rule.
question_mark
Candidate notices that encountering a coin larger than maxConsecutive+1 stops consecutive formation.

warning

常见陷阱

外企场景

error
Not sorting the coins first breaks the greedy extension logic.
error
Miscounting maxConsecutive by off-by-one errors when including 0.
error
Attempting to use dynamic programming unnecessarily increases complexity and misses the greedy invariant insight.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Coins with duplicates only: test the greedy extension with multiple identical coins.
arrow_right_alt
Limited coin values: adjust the approach when the largest coin is significantly bigger than previous sums.
arrow_right_alt
Find non-consecutive maximum sum sequences: analyze failure modes when gaps exist in coin values.

help

常见问题

外企场景

继续练习

#1833 雪糕的最大数量 #1838 最高频元素的频数 #1846 减小和重新排列数组后的最大元素