NC 最长上升子序列(三)

本文主要是介绍NC 最长上升子序列(三)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

系列文章目录

---

---

前言

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。

---

描述
给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）

class Solution {
public:vector<int> LIS(vector<int>& arr) {vector<int> dp(arr.size(), 1); int maxn = 0, n = arr.size();for(int i = 1; i < n; ++i){//找到满足 j < i,arr[j] < arr[i],的最大dp[j]进行转移int res = 0;for(int j = 0; j < i; ++j){if(arr[i] > arr[j]) {res = max(res, dp[j]); }}dp[i] = res + 1;//加上arr[i]maxn = max(maxn, dp[i]); //找到最大长度}vector<int> ans(maxn);for(int i = n - 1, j = maxn; j > 0; --i){ //逆向找到第一个满足所需大小的数if(dp[i] == j){ ans[--j] = arr[i];//填入后继续寻找下一个数}}return ans;}
};

这篇关于NC 最长上升子序列(三)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---