专栏首页图灵技术域算法基础-最长递增子序列

算法基础-最长递增子序列

【问题1】最长递增子序列问题 【问题描述】设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<ak1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。 采用一个数组temp[]保存 以当前元素结尾的最长递增子序列长度,最后求出全局最优解 更新最长递增子序列的条件:a[i]>a[j] (i>j) 且前一个递增序列长度大于等于当前递增序列长度

动态规划:

代码(不重复的子序列)

C++

#include<iostream>
#define MAX 100
using namespace std;
int main()
{
    int num[MAX],temp[MAX];
    int i,j,n,maxl,m;
    while(cin>>n)
    {
        temp[0]=1;
        maxl=0;
        for(i=0;i<n;i++)
            cin>>num[i];
        for(i=1;i<n;i++)
        {
            m=0;
            for(j=0;j<i;j++)
            {
                if(num[i]>num[j]&&temp[j]>m)
                    m=temp[j];
            }
            temp[i]=m+1;
            if(temp[i]>maxl)
                maxl=temp[i];
        }
        cout<<maxl<<endl;
    }
}

几个解释得较好的链接,供学习用:

http://blog.csdn.net/u013074465/article/details/45442067

http://blog.csdn.net/joylnwang/article/details/6766317

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最长递增子序列

    最长递增序列不要求数组元素连续问题,返回递增序列长度和递增序列。o(n^2)做法,顺序比较以第i个元素开头的递增序列即可。 利用动态规划来做,假设数组为1, -...

    机器学习算法工程师
  • 【C++】算法集锦(13):最长递增子序列

    输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

    看、未来
  • 最长单调递增子序列

    动态规划问题: 令dp[i]表示:在str[0-i]中,当以str[i]为单调递增子序列最后一个元素时,所得最长单调递增子序列的长度。 递推式: dp[0]=1...

    用户1215536
  • 单调递增最长子序列

    求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4

    书童小二
  • Leetcode|线性序列|300. 最长递增子序列

    【本题dp数组定义】:dp[i]表示前i个元素中最长递增子序列长度(必须包含第i个尾元素, 否则无法确定状态如何转移)

    SL_World
  • 动态规划:最长递增子序列

    题目链接:https://leetcode-cn.com/problems/longest-increasing-subsequence/

    代码随想录
  • 最长连续递增子序列问题

    给定一个长度为N的数组,给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1...

    xujjj
  • 画解算法 674-最长连续递增序列

    https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

    灵魂画师牧码
  • 回溯算法:递增子序列

    题目链接:https://leetcode-cn.com/problems/increasing-subsequences/

    代码随想录
  • hdu----(1950)Bridging signals(最长递增子序列 (LIS) )

    Bridging signals Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65536/3...

    Gxjun
  • 【一天一道Leetcode】最长递增子序列长度

    子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。

    潘永斌
  • HOJ 2985 Wavio Sequence(最长递增子序列以及其O(n*logn)算法)

    Wavio Sequence My Tags (Edit) Source : UVA Time limit : 1 sec Memor...

    ShenduCC
  • 1-9 最长连续递增子序列 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • LeetCode 673. 最长递增子序列的个数(DP)

    Michael阿明
  • 674. 最长连续递增序列

    Michel_Rolle
  • Leetcode:最长连续递增序列

    连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序...

    Liusy
  • 674. 最长连续递增序列

    CaesarChang张旭
  • LeetCode 674. 最长连续递增序列

    题目链接:https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

    Michael阿明
  • 动态规划应用--最长递增子序列 LeetCode 300

    有一个数字序列包含n个不同的数字,如何求出这个序列中的最长递增子序列长度?比如2,9,3,6,5,1,7这样一组数字序列,它的最长递增子序列就是2,3,5,7,...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券