find-the-maximum-number-of-elements-in-subset

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 array of positive integers <code>nums</code>.

You need to select a subset of <code>nums</code> which satisfies the following condition:

<ul>
	<li>You can place the selected elements in a 0-indexed array such that it follows the pattern: <code>[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x]</code> (Note that <code>k</code> can be be any non-negative power of <code>2</code>). For example, <code>[2, 4, 16, 4, 2]</code> and <code>[3, 9, 3]</code> follow the pattern while <code>[2, 4, 8, 4, 2]</code> does not.</li>
</ul>

Return the maximum number of elements in a subset that satisfies these conditions.

&nbsp;
Example 1:

<pre>
Input: nums = [5,4,1,2,2]
Output: 3
Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 22 == 4. Hence the answer is 3.
</pre>

Example 2:

<pre>
Input: nums = [1,3,2,4]
Output: 1
Explanation: We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, there may be multiple subsets which provide the same answer. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

maximumLength

Find the Maximum Number of Elements in Subset

Longest Consecutive Sequence

longest-consecutive-sequence

最长连续序列

Array

Hash Table

Enumeration

给你一个 正整数 数组 <code>nums</code> 。

你需要从数组中选出一个满足下述条件的子集：

<ul>
	<li>你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：<code>[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x]</code>（注意，<code>k</code> 可以是任何 非负 的 2 的幂）。例如，<code>[2, 4, 16, 4, 2]</code> 和 <code>[3, 9, 3]</code> 都符合这一模式，而 <code>[2, 4, 8, 4, 2]</code> 则不符合。</li>
</ul>

返回满足这些条件的子集中，元素数量的 最大值 。

&nbsp;

示例 1：

<pre>
输入：nums = [5,4,1,2,2]
输出：3
解释：选择子集 {4,2,2} ，将其放在数组 [2,4,2] 中，它遵循该模式，且 22 == 4 。因此答案是 3 。
</pre>

示例 2：

<pre>
输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>