LFIS

시간 제한3초메모리 제한256 MB

요약

A에서 각 원소가 바로 앞 두 원소의 합 이상이 되는 가장 긴 부분수열의 길이를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색
정답자: 아직 제출이 없습니다

문제

정수 수열 $A$ 의 부분 수열 $B$ 중, 가능한 모든 $i$ 에 대해 다음 조건을 만족하는 수열을 FIS(Fibonacci Increasing Subsequence)라 하자.

$B_{i-2} + B_{i-1} \le B_i$

$A$ 가 주어질 때, 가장 긴 FIS를 구하여라.

입력

첫 번째 줄에 $N$ 이 주어진다. ( $2 \le N \le 10^6$ )

두 번째 줄에 $A$ 의 값이 순서대로 주어진다. ( $0 \le A_i \le 10^9$ )

출력

첫 번째 줄에 가장 긴 FIS의 길이를 출력한다.

힌트

$B$ 가 $A$ 의 부분 수열이라는 것은, $1 \le i_1 < i_2 < \cdots < i_{\lvert B \rvert} \le \lvert A \rvert$ 를 만족하는 $i_1, i_2, \ldots, i_{\lvert B \rvert}$ 가 존재해서 모든 $1 \le j \le \lvert B \rvert$ 에 대해 $A_{i_j} = B_j$ 가 성립한다는 뜻이다.

예제1

예제 1
입력
```
10
6 3 2 3 1 10 4 9 4 3
```
예상 출력
```
4
```