最长上升子序列（DP）

落日映苍穹つ 2022-06-10 10:36 271阅读 0赞

问题描述  
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).  
你的任务，就是对于给定的序列，求出最长上升子序列的长度。

思路:把问题分解成小问题（子问题），再通过自下而上（序列从左至右）的思路，解决小问题递推到解决大问题，最终得到最终解。

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 1010;
    int a[MAXN];    
    int maxLen[MAXN];
    int main() {
        int N;
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> a[i];
            maxLen[i] = 1;
        }
        for (int i = 2; i <= N; i++) {
        //每次求以第i个数为终点的最长上升子序列的长度
            for (int j = 1; j < i; j++) {
            //察看以第j个数为终点的最长上升子序列
                if (a[i] > a[j]) {
                    maxLen[i] = max(maxLen[i], maxLen[j]+1);            
                }
            }
        }
        //输出向量中的最大值 
        cout << * max_element(maxLen+1, maxLen + N + 1);
        return 0;
    } //时间复杂度O(N^2)

发表评论取消回复

表情：

评论列表（有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读

相关 Alignment （DP基础--最长上升子序列）

目录 Alignment （DP基础--最长上升子序列）题目题意思路代码 Alignmen

迷南。/ 2023年06月01日 06:11/ 0 赞/ 7 阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 235 阅读

相关最长上升子序列

问题描述一个数的序列ai，当a1< a2< ... < aS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些

深藏阁楼爱情的钟/ 2022年08月18日 00:40/ 0 赞/ 225 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,

川长思鸟来/ 2022年07月13日 01:55/ 0 赞/ 205 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 236 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

墨蓝/ 2022年07月12日 02:47/ 0 赞/ 259 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 318 阅读

相关最长上升子序列（DP）

问题描述一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列

落日映苍穹つ/ 2022年06月10日 10:36/ 0 赞/ 272 阅读

相关最长上升子序列

最长上升子序列 Time Limit: 3000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Probl

傷城~/ 2022年05月30日 10:09/ 0 赞/ 211 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)

一时失言乱红尘/ 2022年05月16日 01:28/ 0 赞/ 255 阅读