C++ 代码实现 有一个长度为 n 的正整数序列,请找出其中的一个最长的子序列,使得这个子序列中的任意两个数都互质,互质是指两个数的最大公约数为 1。请问这样子序列的最大长度是多少,这样最大长度子序列

可以使用动态规划来解决这个问题。具体来说，我们可以定义一个长度为 n 的状态数组 dp，其中 dp[i] 表示以第 i 个数为结尾的最长子序列长度。

对于 dp[i]，我们可以枚举它前面的所有数 j（j < i），如果第 j 个数和第 i 个数互质，那么可以将第 j 个数加入以第 i 个数结尾的子序列中，从而得到一个新的长度为 dp[j]+1 的子序列。我们只需要在所有能够得到新子序列的 j 中取最大的 dp[j]+1，就得到了 dp[i] 的值。

最终的答案就是 dp 数组中的最大值。下面是相应的 C++ 代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;

int a[MAXN], dp[MAXN];

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = 1; // 初始状态为 1
    }

    int ans = 1; // 最终答案
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (gcd(a[i], a[j]) == 1) {
                dp[i] = max(dp[i], dp[j] + 1); // 转移方程
            }
        }
        ans = max(ans, dp[i]); // 更新最终答案
    }

    cout << ans << endl;
    return 0;
}