AcWing 4489. Longest subsequence

Original link ：4489. The longest subsequence - AcWing Question bank

Given a length of  nn  Of Strictly monotonically increasing Integer sequence of  a1,a2,…,an.

Sequence  aa  The subsequence of can be expressed as  ai1,ai2,…,aipai1,ai2,…,aip, among  1≤i1<i2<…<ip≤n1≤i1<i2<…<ip≤n.

We hope to find one  aa  The subsequence , Make the subsequence satisfy ： about  j∈[1,p−1]j∈[1,p−1],aij+1≤aij×2 Hang up .

We think , The length is  11  The subsequence of always satisfies the condition .

Please calculate and output the maximum possible length of the subsequence that meets the conditions .

Input format

The first line contains an integer  n.

The second line contains  n  It's an integer  a1,a2,…,an.

Output format

An integer , Represents the maximum possible length of the subsequence that meets the condition .

Data range

front  5  Test points meet  1≤n≤10.
All test points meet  1≤n≤2×10^5,1≤a1<a2<…<an≤10^9.

sample input 1：

10
1 2 5 6 7 10 21 23 24 49

sample output 1：

4

sample input 2：

5
2 10 50 110 250

sample output 2：

1

sample input 3：

6
4 7 12 100 150 199

sample output 3：

3

  Ideas 1： greedy

 AC Code ：

#include <iostream>

using namespace std;

const int MAXN = 2e5 + 7;
int arr[MAXN], n, ans = 1, cnt = 1;

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    for (int i = 1; i <= n - 1; i++) {
        if (arr[i + 1] <= arr[i] * 2) {
            cnt++;
        } else {
            ans = max(ans, cnt);
            cnt = 1;
        }
    }
    // Pay attention to the last ans by max(ans, cnt)  Because it was last updated cnt Not with ans Compare 
    cout << max(ans, cnt) << endl;

    return 0;
}

Ideas 2：dp 

Let the original sequence be arr[1~n] set up dp[1~n] Array , The initial value is 1
Traversal array 2~n, if a[i−1]∗2 ≥ a[i] , that dp[i]=dp[i-1]+1

AC Code ：

/*
* @Author: Spare Lin
* @Project: AcWing2022
* @Date: 2022/7/2 21:10
* @Description: dp practice 
*/

#include <iostream>

using namespace std;

const int MAXN = 2e5 + 7;

int dp[MAXN], arr[MAXN], n, ans = 0;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        dp[i] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        if(arr[i] <= arr[i - 1] * 2) {
            dp[i] = max(dp[i], dp[i - 1] + 1);
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}