maximum-number-of-consecutive-values-you-can-make

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>coins</code> of length <code>n</code> which represents the <code>n</code> coins that you own. The value of the <code>ith</code> coin is <code>coins[i]</code>. You can make some value <code>x</code> if you can choose some of your <code>n</code> coins such that their values sum up to <code>x</code>.

Return the maximum number of consecutive integer values that you can make with your coins starting from and including <code>0</code>.

Note that you may have multiple coins of the same value.

&nbsp;
Example 1:

<pre>
Input: coins = [1,3]
Output: 2
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
You can make 2 consecutive integer values starting from 0.</pre>

Example 2:

<pre>
Input: coins = [1,1,1,4]
Output: 8
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.</pre>

Example 3:

<pre>
Input: coins = [1,4,10,3,1]
Output: 20</pre>

&nbsp;
Constraints:

<ul>
	<li><code>coins.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 4 * 104</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 4 * 104</code></li>
</ul>

getMaximumConsecutive

Maximum Number of Consecutive Values You Can Make

Patching Array

patching-array

按要求补齐数组

Greedy

Array

Sorting

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

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

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

 

示例 1：

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

示例 2：

<pre>
输入：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 个连续整数。</pre>

示例 3：

<pre>
输入：nums = [1,4,10,3,1]
输出：20</pre>

 

提示：

<ul>
	<li><code>coins.length == n</code></li>
	<li><code>1 <= n <= 4 * 104</code></li>
	<li><code>1 <= coins[i] <= 4 * 104</code></li>
</ul>