【每日算法 && 数据结构(C++)】—— 13 | 求最长自增子序列（解题思路、流程图、代码片段）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日算法 && 数据结构(C++)】—— 13 | 求最长自增子序列（解题思路、流程图、代码片段）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【每日算法 && 数据结构(C++)】—— 13 | 求最长自增子序列（解题思路、流程图、代码片段）,浅浅的刷亿点题吧,算法,数据结构,c++

Today’s quote is: "Actions speak louder than words.

今天的一句话是：“行动胜于言辞

01 | 👑 题目描述

求最长递增子序列

最长递增子序列是指在给定序列中，找到一个最长的子序列，使得子序列中的元素按照递增的顺序排列。

例如，对于序列 [1, 3, 2, 5, 4, 7, 6]，其中的最长递增子序列可以是 [1, 2, 4, 6] 或者 [1, 3, 5, 7]。这些子序列中的元素按照递增的顺序排列，且长度为4，是该原始序列中最长的递增子序列。

02 | 🔋 解题思路

求解最长递增子序列可以使用动态规划的方法，下面是一种常用的解题思路和流程：

定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。
初始化 dp 数组，将所有元素的初始值设为 1，即每个元素自身都可以构成一个长度为 1 的递增子序列。
从左到右遍历原始序列，对于每个位置 i，比较其前面的所有位置 j（j = 0 to i-1），如果 nums[i] 大于 nums[j]，说明 nums[i] 可以接在 nums[j] 后面形成一个更长的递增子序列。此时更新 dp[i] 的值为 max(dp[i], dp[j] + 1)。
遍历完整个序列后，dp 数组中的最大值即为最长递增子序列的长度。
为了还原最长递增子序列本身，我们可以在更新 dp 数组的过程中，记录每个位置 i 的最佳前驱位置 prev[i]，表示以第 i 个元素结尾的最长递增子序列的前驱元素的位置。通过这个 prev 数组，我们可以从最后一个元素开始，通过不断回溯找到整个最长递增子序列。
最后，根据 prev 数组和最长递增子序列的长度构建最长递增子序列。

时间 && 空间复杂度

时间复杂度：O(n^2)
嵌套的两个循环遍历，外层循环遍历 n 次，内层循环遍历 i 次（i = 0 to n-1）
空间复杂度：**O(n) **
使用了一个长度为 n 的数组 dp 来存储每个位置的最长递增子序列长度，以及一个长度为 n 的数组 prev 来存储每个位置的最佳前驱位置

03 | 🧢 代码片段

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> longest_increasing_subsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> prev(n, -1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
    }

    int max_len = *max_element(dp.begin(), dp.end());
    int idx = find(dp.begin(), dp.end(), max_len) - dp.begin();

    vector<int> sequence;
    while (idx != -1) {
        sequence.push_back(nums[idx]);
        idx = prev[idx];
    }

    reverse(sequence.begin(), sequence.end());

    return sequence;
}

int main() {
    vector<int> nums = {1, 3, 2, 5, 4, 7, 6};
    vector<int> result = longest_increasing_subsequence(nums);

    cout << "Longest Increasing Subsequence: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}