AcWing 4489. 最长子序列

原题链接：4489. 最长子序列 - AcWing题库

给定一个长度为 nn 的严格单调递增的整数序列 a1,a2,…,an。

序列 aa 的子序列可以表示为 ai1,ai2,…,aipai1,ai2,…,aip，其中 1≤i1<i2<…<ip≤n1≤i1<i2<…<ip≤n。

我们希望找到一个 aa 的子序列，使得该子序列满足：对于 j∈[1,p−1]j∈[1,p−1]，aij+1≤aij×2恒成立。

我们认为，长度为 11 的子序列总是满足条件的。

请你计算并输出满足条件的子序列的最大可能长度。

输入格式

第一行包含一个整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示满足条件的子序列的最大可能长度。

数据范围

前 5 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤2×10^5，1≤a1<a2<…<an≤10^9。

输入样例1：

10
1 2 5 6 7 10 21 23 24 49

输出样例1：

4

输入样例2：

5
2 10 50 110 250

输出样例2：

1

输入样例3：

6
4 7 12 100 150 199

输出样例3：

3

 思路1：贪心

 AC代码：

#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;
        }
    }
    //注意最后ans为max(ans, cnt) 因为最后一次更新的cnt还未与ans进行比较
    cout << max(ans, cnt) << endl;

    return 0;
}

思路2：dp 

设原始数列为arr[1~n] 设dp[1~n]数组，初始值为1
遍历数组2~n，若a[i−1]∗2 ≥ a[i] ，那么dp[i]=dp[i-1]+1

AC代码：

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

#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;
}