最长递增子序列问题动态规划c++

最长递增子序列（Longest Increasing Subsequence，简称LIS）是指在一个无序的序列中，找到一个子序列，使得这个子序列中的元素是递增的，并且这个子序列的长度尽可能地长。动态规划是解决该问题的一种常用方法。

动态规划算法步骤如下：
1. 定义状态：dp[i] 表示以第 i 个元素为结尾的最长递增子序列长度；
2. 初始化状态：dp[i]=1，因为每个元素本身都是一个长度为1的递增子序列；
3. 状态转移方程：在前 i-1 个元素中，找到比第 i 个元素小的元素 j，状态转移方程为 dp[i]=max(dp[j])+1；
4. 最终结果：遍历 dp 数组，找到最大值即为所求。

以下是C++代码实现：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // 初始化状态
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1); // 状态转移方程
            }
        }
        res = max(res, dp[i]); // 更新最大值
    }
    return res;
}

相关问题

最长递增子序列问题c++动态规划

最长递增子序列（Longest Increasing Subsequence，简称LIS）问题是一个经典的计算机科学问题，它被定义为：给定一个序列，找到最长的子序列（可以不连续）使得其中的元素按照顺序递增。

C++中可以使用动态规划算法解决该问题。具体步骤如下：

1. 定义一个数组dp，其中dp[i]表示以第i个元素结尾的最长递增子序列长度。

2. 初始化dp数组，将所有元素的dp值初始化为1。

3. 对于每个元素i，遍历其前面的所有元素j（j<i），如果第j个元素小于第i个元素，那么将dp[i]更新为dp[j]+1。

4. 遍历整个dp数组，找到其中最大的值max，即为最长递增子序列的长度。

5. 可以使用一个辅助数组prev来记录最长递增子序列中每个元素的前一个元素位置，从而还原出最长递增子序列。

以下是C++代码示例：

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

int LIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> prev(n, -1);
    int max_len = 1;
    int end = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            end = i;
        }
    }
    vector<int> lis;
    while (end != -1) {
        lis.push_back(nums[end]);
        end = prev[end];
    }
    reverse(lis.begin(), lis.end());
    for (int i = 0; i < lis.size(); i++) {
        cout << lis[i] << " ";
    }
    cout << endl;
    return max_len;
}

int main() {
    vector<int> nums = {3, 4, -1, 0, 6, 2, 3};
    int len = LIS(nums);
    cout << len << endl;
    return 0;
}

最长递增子序列返回子序列C++代码

这是一个经典算法问题，可以使用动态规划求解。

假设原序列为 A，长度为 n，则令 dp[i] 表示以 A[i] 为结尾的最长递增子序列的长度。

初始时，所有 dp[i] 的值都为 1，因为一个数本身就是一个长度为 1 的递增子序列。

然后使用两重循环枚举 i 和 j（i < j），如果 A[i] < A[j]，则 dp[j] = max(dp[j], dp[i] + 1)。

这个算法时间复杂度为 O(n^2)。

最终的最长递增子序列长度为 max(dp[i])，可以使用额外的数组来记录具体的子序列。

以下是一个示例代码：

vector<int> LIS(vector<int>& A) {
int n = A.size();
vector<int> dp(n, 1), pre(n, -1);
int maxlen = 1, maxidx = 0;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (A[j] < A[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] > maxlen) {
maxlen = dp[i];
maxidx = i;
}
}
vector<int> res(maxlen);
for (int i = maxlen - 1; i >= 0; --i) {
res[i] = A[maxidx];
maxidx = pre[maxidx];
}
return res;
}