問題一覧 > 通常問題

No.2218 Multiple LIS

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 154
作問者 : stoq / テスター : ぷら Shirotsume
お気に入りにしたユーザー ProblemId : 7703 / 自分の提出
問題文最終更新日: 2023-02-18 08:26:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 377 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_1,\dots,A_N)$ of length $N$.
Find the maximum length of a not necessarily contiguous subsequence $(B_1,\dots,B_k)$ of $A$ that satisfies the following condition.

  • For every $1 \leq i \leq k-1$, $B_{i+1}$ is a multiple of $B_i$.
    Note that a subsequence of length $1$ always satisfies the condition.

Input

$N$
$A_1$ $\dots$ $A_N$

  • All inputs are integers.
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^5$

Output

Output the maximum length of a subsequence that satisfies the condition.

Sample

Sample 1
Input
6
1 2 3 4 4 5
Output
4

For example, the subsequence $(1,2,4,4)$ satisfies the condition.

No longer subsequence satisfies the condition, so the maximum length is $4$.

Sample 2
Input
1
1
Output
1

Sample 3
Input
10
3 2 9 1 9 7 18 8 36 1
Output
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。