精华内容
下载资源
问答
  • 给出一个由n个数组成的序列x[1..n],找出它的最长单调上升序列的长度。即找出最大的长度ma1, a2……,am,使得 a1 < a2 < … … < am 且 x[a1] < x[a2] < … … < x[am]。 I...
    Font Size:Aa Aa Aa

    Description

         给出一个由n个数组成的序列x[1..n],找出它的最长单调上升子序列的长度。即找出最大的长度m和a1,
    a2……,am,使得  a1 < a2 < … … < am 且 x[a1] < x[a2] < … … < x[am]。

    Input

    先输入一个整数t(t<=200)。代表測试组数。

    每组数据先输入一个N,代表有N个数(1<=N<=1000). 输入N个正整数,a1。a2,a3.....an(0<=ai<=100000).

    Output

    每组输出一个整数。代表最长的长度。

    Sample Input

    1
    7
    1  7  3  5  9  4  8

    Sample Output

    4



    代码例如以下:
    #include <stdio.h>
    #define maxn 1005
    int a[maxn];
    int dp[maxn];
    int max(int x,inty)
    {
        returnx>y?

    x:y;

    }
    int main()
    {
        intt,n;
          
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            inti,j;
            for(i=1;i<=n;i++)
                scanf("%d",&a[i]);
            for(i=0;i<=n;i++)
                dp[i]=1;
            intans=0;
            for(i=1;i<=n;i++)
            {
                for(j=1;j<i;j++)
                    if(a[j]<a[i])
                        dp[i]=max(dp[i],dp[j]+1);
                ans=max(dp[i],ans);
            }
            printf("%d\n",ans);
        }
        return0;
    }

    转载于:https://www.cnblogs.com/yutingliuyl/p/6705560.html

    展开全文
  • 其中dp[i][0]代表从最开始到i位置上的最长上升序列的长度,但不一定包含位置i; dp[i][1]代表最开始到i位置上的最长上升序列中,末尾的那个元素的大小; 但是这种方法很蠢,它没有办法解决:10,9,2,5,3,4这种...

    在这里插入图片描述

    分析

    我一开始的想法是,定义一个二维dp数组,dp[len][2];
    其中dp[i][0]代表从最开始到i位置上的最长上升子序列的长度,但不一定包含位置i;
    dp[i][1]代表最开始到i位置上的最长上升子序列中,末尾的那个元素的大小;
    但是这种方法很蠢,它没有办法解决:10,9,2,5,3,4这种问题,因为它没有办法判断出2,5和2,3,4;

    正常题解也是动态规划,依旧是需要知道子序列的末尾元素,才能去判断大小;
    因此定义dp[i]为以nums[i]结尾的最长子序列的长度,那么只要找到位置i之前的所有元素中,大小比nums[i]小的元素,并找出这些大小比nums[i]小的元素中dp最大(子序列最长)的那一个,然后把位置i的元素接着它后面就是以位置i结尾的最长子序列了;
    详细见:
    https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

    代码

    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int len = nums.size();
            if(len==0)
            return 0;
            int *dp = new int[len];
            dp[0] = 1;
            int res = 1;
            for(int i=1;i<len;i++)
            {
                int max_dp = 0;
                for(int j=0;j<i;j++)
                {
                    if(nums[j]<nums[i])
                    max_dp = max(max_dp,dp[j]);
                }
                dp[i] = max_dp + 1;
                res = max(res,dp[i]);
            }
            return res;
        }
    };
    
    展开全文
  • dp之最长上升序列

    2013-04-24 15:11:30
    经过分析,发现 “求以ak(k=1, 2, 3…N)为终点的最长上升序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数,称为该子序列的“终点”。虽然这个子问题原问题形式上并不完全一样,但是只要...

    问题描述

    一个数的序列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).

    你的任务,就是对于给定的序列,求出最长上升子序列的长度。

     

     

     

    解题思路

    如何把这个问题分解成子问题呢?经过分析,发现 “求以ak(k=1, 2, 3…N)为终点的最长上升子序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数,称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样,但是只要这N个子问题都解决了,那么这N个子问题的解中,最大的那个就是整个问题的解。

    由上所述的子问题只和一个变量相关,就是数字的位置。因此序列中数的位置k 就是“状态”,而状态 k 对应的“值”,就是以ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有N个。状态定义出来后,转移方程就不难想了。假定MaxLen (k)表示以ak做为“终点”的最长上升子序列的长度,那么:

    MaxLen (1) = 1

    MaxLen (k) = Max { MaxLen (i):1<i < k 且 ai < ak且 k≠1 } + 1

    这个状态转移方程的意思就是,MaxLen(k)的值,就是在ak左边,“终点”数值小于ak,且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列,加上ak后就能形成一个更长的上升子序列。

    实际实现的时候,可以不必编写递归函数,因为从 MaxLen(1)就能推算出MaxLen(2),有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3)

    #include <stdio.h>
    #define  MAX 1000
    int seq[MAX+10];
    int seqlen[MAX+10];
    int main()
    {
    	int i,j,k,N,max,maxlen=1;
    	for(i=1;i<=9;i++)
    		seqlen[i]=1;               //seqlen数组存以第i个数为终点的最长上升序列
    	scanf("%d",&N);
    	for(i=1;i<=N;i++)
    		scanf("%d",&seq[i]);       //seq数组保存序列数组
    	for (i=2;i<=N;i++)
    	{
    		max=0;
    		for (j=1;j<=i-1;j++)
    		{
    			if(seq[j]<seq[i]&&seqlen[j]>max)  //在前i-1个序列中,寻找以终点小于seq[i]的最长的子序列,即最优子状态
    				max=seqlen[j];
    		}
    		seqlen[i]=max+1;
    		if(seqlen[i]>maxlen)           //seqlen中保存的是第i个数为终点的最长上升序列,找出这个数组中最大的值即为最优序列长度
    			maxlen=seqlen[i];
    	}
    	printf("%d/n",maxlen);
    	return 0;
    }

    转至http://blog.csdn.net/chenwenshi/article/details/6027086
    展开全文
  • 经过分析,发现 “求以ak(k=1, 2, 3…N)为终点的最长上升序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数,称为该子序列的“终点”。虽然这个子问题原问题形式上并不完全一样,但是只要...
    

    问题描述

    一个数的序列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).

    你的任务,就是对于给定的序列,求出最长上升子序列的长度。

     

     

     

    解题思路

    如何把这个问题分解成子问题呢?经过分析,发现 “求以ak(k=1, 2, 3…N)为终点的最长上升子序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数,称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样,但是只要这N个子问题都解决了,那么这N个子问题的解中,最大的那个就是整个问题的解。

    由上所述的子问题只和一个变量相关,就是数字的位置。因此序列中数的位置k 就是“状态”,而状态 k 对应的“值”,就是以ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有N个。状态定义出来后,转移方程就不难想了。假定MaxLen (k)表示以ak做为“终点”的最长上升子序列的长度,那么:

    MaxLen (1) = 1

    MaxLen (k) = Max { MaxLen (i):1<i < k 且 ai < ak且 k≠1 } + 1

    这个状态转移方程的意思就是,MaxLen(k)的值,就是在ak左边,“终点”数值小于ak,且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列,加上ak后就能形成一个更长的上升子序列。

    实际实现的时候,可以不必编写递归函数,因为从 MaxLen(1)就能推算出MaxLen(2),有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3)……

     

    01.#include <stdio.h>  
    02.#define  MAX 1000  
    03.int seq[MAX+10];  
    04.int seqlen[MAX+10];  
    05.int main()  
    06.{  
    07.    int i,j,k,N,max,maxlen=1;  
    08.    for(i=1;i<=9;i++)  
    09.        seqlen[i]=1;               //seqlen数组存以第i个数为终点的最长上升序列  
    10.    scanf("%d",&N);  
    11.    for(i=1;i<=N;i++)  
    12.        scanf("%d",&seq[i]);       //seq数组保存序列数组  
    13.    for (i=2;i<=N;i++)  
    14.    {  
    15.        max=0;  
    16.        for (j=1;j<=i-1;j++)  
    17.        {  
    18.            if(seq[j]<seq[i]&&seqlen[j]>max)  //在前i-1个序列中,寻找以终点小于seq[i]的最长的子序列,即最优子状态  
    19.                max=seqlen[j];  
    20.        }  
    21.        seqlen[i]=max+1;  
    22.        if(seqlen[i]>maxlen)           //seqlen中保存的是第i个数为终点的最长上升序列,找出这个数组中最大的值即为最优序列长度  
    23.            maxlen=seqlen[i];  
    24.    }  
    25.    printf("%d/n",maxlen);  
    26.    return 0;  
    27.}  
    

    展开全文
  • 最长上升序列可以说是最常见的dp了,所以它可以一些思想结合或者优化它本身,题目变形也多,难度也会稍微高数字三角形模型,个人感觉。 ps:中间有些题在落谷也有,落谷数据是加强过的,所以如果该题落谷有数据...
  • 动态规划之最长上升序列(入门版)

    千次阅读 多人点赞 2019-02-26 16:56:23
     比如:序列(100, 1, 2, 3)的最大上升子序列和为100,而最长上升子序列为(1, 2, 3)。 现在我们要解决的问题就是在给定的数组中找出最长上升序列:先给一个栗子 给定的数组 a[7] = {1,6,4,2,3,9,8} 思想:这里...
  • 题目思路:使用lower_boundupper_bound,以最长上升序列举例,如果新来的元素大于目前维护的序列的最后一个元素,那就加进来,如果比他小,那么就用lower_bound获得第一个大于它的数字的位置,并代替它,所以...
  • 给定N个数,求这N个数的最长上升序列的长度。 【样例输入】 7 2 5 3 4 1 7 6 【样例输出】 4 什么是最长上升序列? 就是给你一个序列,请你在其中求出一段不断严格上升的部分,它不一定要连续。 就像这样:2,3,4...
  • 用LCS解决LIS问题最长上升序列有它的套路,不过用LCS算法是可以解决的: ...第三步:对AAB′B^{'}做LCS运算,即可得出原序列AA的LIS最长上升序列。好,这个算法在LeetCode是Memory Limit代码class So
  • 我仅调整了B序列的顺序,使最初不为顺序序列(因为我的代码实现在这里栽了跟斗orz)。 关于(LCS)为什么可以转化成LIS问题,这里提供一个解释。 比如这样的两个序列: A:3 2 1 4 5 B:2 5 4 1 3 我们不妨给它...
  • 元组的风暴之最长上升序列 小美:还记得我们上次做的那道题目吗?求最长连续递增子序列的长度。 阿福:记得啊,当时我们用了两种方法,分别是在a[i] <=a[i-1]a[i] > a[i-1]时更新max_len,古老师还表扬...
  • python_lintcode_397最长上升连续子序列_56两数之和
  • 最大上升序列之和

    2021-02-02 15:30:58
    题目中已告诉最长上升序列之和!=最大上升子序列之和 动态规划的比较重要的点 1. 拆分成子问题 2. 状态转移方程 (其实动态规划也可以理解为递归的逆过程) 根据这道题来实操一下 拆分成子问题 求的是n个数的...
  • 编程帮助政府做出一些批准拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。 输入格式 第1行,一个整数N,表示城市数。 第2行到第n+1行,每行两个整数,中间用1个空格隔开,分别表示...
  • 题意:用之前的每一个数当前的数比较,比当前数小的就加上dp【之前数】,不然就等于当前数 #include #include #define INF 0x3f3f3f3f int num[ 1010 ]; int dp[ 1010 ]; int max( int a, int b...
  • 就是说给你两个序列x={x1,x2,x3……,xm}y={y1,y2,y3,……,ym}找出xy的一个最长的公共子序列。 思路:如果是暴力枚举则为枚举x序列的所有子序列,检查每个子序列是否也是y的子序列,记录找到最长的公共子序列,...
  • 动态规划贪心算法的知识点 动态规划的核心思想是把原问题分解成子问题进行求解,也就是分治...给定一个无序的整数数组,找到其中最长上升序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的...
  • 经典解法:也是传统解法,动态规划,每加入一个新的数字,则检查是否前面所记录的序列能组成更长序列。示例如下: 扫描序列 1 -1 2 -3 4 …… 记录序列最大值 1 -1 2 1 4 …… 记录序列长度 1
  • 给定一个无序的整数数组,找到其中最长上升序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是&nbsp;[2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升序列的...
  • 解题心得: 1、注意动态转移方程式,d[j]+1>d[i]>?d[i]=d[j]+1:d[i] 2、动态规划的基本思想:将大的问题化为小的,再逐步扩大得到答案,但是小问题的基本性质要大的...1180: 最长上升序列之基础 Tim...
  • 对于一个给定的数组,它的最长上升序列不一定唯一,但是最长上升序列的长度一定是确定的。 这里我给出两种方法分别是dpO(n2)的贪心+二分的算法。 (1)动态规划dp。 我们可以想想所以可以用动态规划是因为...
  • 数字三角形问题:问题描述:问题分析:程序代码:(递归法和动归法)# -*- coding: utf-8 -*- """...如上三角形,找出一条从顶部到底部的路径,使得路径所经过的数字之和最大。 要...
  • P2642 双子序列最大和 题目描述给定一个长度为n的整数序列,要求从中选出两个连续子序列,使得这两个连续子序列序列之和最大,最终只需输出最大和。一个连续子序列的和为该子序列中所有数之和。每个连续子序列的...
  • 给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序原串中的顺序一致。 样例输入 abcfbc abfcab programming contest abcd mnp 样例输出 ...
  • 2018.01.07 动态规划练习 1.最长上升子序列和 ...这样就要注意一个点:最长的上升子序列之和不一定最大。 状态转移方程:sum[i]=_Max(sum[i],sum[j]+num[i]); (j<i,num[j]<num[i]) 核...
  • 1、记忆化数组 2.、动态规划思想 递归定义-&amp;amp;gt; 递推公式 ...路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 189
精华内容 75
关键字:

最长上升序列之和