精华内容
下载资源
问答
  • 最长升序子序列

    千次阅读 2019-04-22 13:01:15
    最长升序子序列 有两种算法,算法的时间复杂度分别是O(n^2)和O(nlogn) O(n^2) dp[i] 指从0~i的最大子升序 但此时的最大值并不一定时最长升序子序列 #include <stdio.h> #include <iostream> using ...

    最长升序子序列

    有两种算法,算法的时间复杂度分别是O(n^2)和O(nlogn)
    O(n^2)
    dp[i] 指从0~i的最大子升序
    但此时的最大值并不一定时最长升序子序列

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    int a[100005];
    int dp[100005];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i = 0;i < n;i++){
    		scanf("%d",a+i);
    		int maxn = 0;
    		//求升序在a[i]的值,
    		//那么a[j]肯定要小于a[i]
    		//找到a[j] < a[i],并且dp[j]最大的值赋值给maxn
    		for(int j = 0;j < i;j++){
    			if(a[j] < a[i]){//如果是等于,那么就可以相等if(a[j] <= a[i]),这是非降序
    				maxn = max(dp[j],maxn);
    			}
    		}
    		//maxn已经是最大并且j<i ,那么加上1就好了 
    		dp[i] = maxn+1;
    	}
    	//为了找到最大值
    	maxn = dp[0];
    	for(int i = 0;i < n;i++){
    		maxn = max(dp[i],maxn);
    	}
    	printf("%d\n",maxn);
    	return 0;
    }
    

    O(nlogn)
    定义一个数组f,设数组的元素为len
    如果此时的x>f[len-1] ,那么就把x添加到数组f的末尾中,并且数组f的个数+1
    如果小于那么就在数组f中从开始往后遍历,替换第一个大于等于x的,因为是上升,所以相邻两个不能相等
    比如
    f[10000] = {1,2,3,10,13,}
    x = 10
    ,此时的x应该是替换f数组中的10,而不是13
    所以就就应该用lower_bound,所以是找到第一个大于等于x的下标
    结果就是len

    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    int f[300005];
    int main()
    {
    	int n;
    	int len = 0;
    	while(~scanf("%d",&n)){
    		len = 0;
    		for(int i = 0;i < n;i++){
    			int x;
    			scanf("%d",&x);
    			if(len == 0) f[len++] = x;
    			else if(x>f[len-1]) f[len++] = x;
    			else {
    				int k = lower_bound(f,f+len,x)-f;
    				f[k] = x;
    			}
    		} 
    		printf("%d\n",len);
    	}
    	return 0;
    }
    
    展开全文
  • 求一个数组中最长升序子序列的长度。如 [8,4,7,5,1,3,6,2]; 升序子序列有 [4,7],[4,5,6],[1,3,6],最长升序子序列的长度为 3。

    算法 - 求最长升序子序列长度

    1. 案例

    求一个数组中最长升序子序列的长度。如 [8,4,7,5,1,3,6,2]; 升序子序列有 [4,7],[4,5,6],[1,3,6],最长升序子序列的长度为 3。

    特别说明:因为题目要求是找到最长升序子序列的长度,并没有说找到最长升序子序列。所以在实现的过程中,只要找到一个子序列。这个子序列是升序的,并且保证是最长的。就可以知道其长度

    2. 思路

    方法:动态规划 + 二分查找

    该方法的解题关键在于,先找到第一个升序子序列(把第一个元素移动到一个空数组,将该数组作为第一个升序子序列)。剩余的元素比这个子序列的最后一个元素大,则直接移动到该子序列尾部。否则在该序列中找到比其大的最小元素,将其替换掉。替换不会影响最长升序子序列的长度,其目的是为了让子序列里面的元素降到最小,好让剩余的元素中数值较大的元素升序排列

    比如数组 [8,4,7,5,1,3,6,2] 中第一个升序序列可以理解为是 [8]。后面的元素 4 比 8 小,就替换掉 8。这个升序序列就是 [4]。接着是 [4,7],找到 5 时,5 比 7 小。找到 [4,7] 中比 5 大的最大元素,替换掉成为 [4,5]。这是为了让后面的较大元素能够升序排列。如果不替换掉 7,后面的元素 6 就没法添加到这个序列中来。这里有点绕,但也是理解这个思路的关键所在。

    第一步:创建新数组
    定义一个新数组 newArr=[],先将数组 arr = [8,4,7,5,1,3,6,2] 中的第一个元素移动到新数组,即 newArr=[8],arr = [4,7,5,1,3,6,2] 。

    第二步:按照二分查找对比元素。
    循环数组 arr 。通过二分查找法找到当前元素 arr[0] (因为每操作一次都会删除掉一个元素,所以当前元素永远是第一个元素)在新数组 newArr 中的位置。

    1. 当前元素与新数组的中间元素比较,当前元素小。左移,还小,继续左移。直到当前元素比中间元素 m 大,则替换掉 m+1 索引位置的元素。如果 m 是 0,则直接替换掉第一个元素。

      如:当前元素为 4,在数组 [3,5,6,7,9] 中找到中间元素 6。当前元素4比6小,左移,将范围定位到 [3,5,6] 。继续找到中间元素 5。当前元素还小,继续左移。将范围定位到 [3,5]。中间元素为 5。当前元素还小,将范围定位到 [3]。当前元素4比3大。替换 m+1 索引位置的元素,也就是用 4 替换 5。结果为 [3,4,6,7,9]。

    2. 当前元素与新数组的中间元素比较,当前元素大,右移。还大,继续右移。直到当前元素比中间元素 m 小,则替换掉 m 索引位置的元素。如果没有找到比当前元素还大的数。则将当前元素直接添加到新数组尾部。

      如:当前元素为 8,在数组 [3,5,6,7,9] 中找到中间元素 6 ,当前元素8比6大,右移,将范围定位到 [6,7,9],继续找到中间元素 7。当前元素还大小,继续右移。将范围定位到 [7,9]。中间元素为 9。当前元素8比9小。替换 m 索引位置的元素,也就是用 9 替换 8。结果为 [3,4,6,7,8]。

    3. 代码

      var arr = [8,4,7,5,1,3,6,2];
     function lengthOfLIS(arr) {
         //判断是否为数组类型
         if(Array.isArray(arr)){
             //如果数组为空直接返回0
             if(arr.length === 0){
                 return 0;
             }
             var newArr = [];
             //先将第一个元素移动到新数组中
             newArr.push(arr.shift());
             while (arr.length){
                 //如果当前元素大于新数组的最后一个元素,则直接将当前元素添加进来
                 if(arr[0]>newArr[newArr.length-1]){
                     newArr.push(arr.shift());
                 }else {
                     //否则用二分查找法找到新数组中比当前元素大的最小元素,将其替换掉
                     var i = 0,j = newArr.length;
                     while (i<j){
                         var m = Math.floor((i+j)/2);
                         if(arr[0]>newArr[m])i=m+1;//当前元素大于中间元素,往右移
                         else j = m;//当前元素小于中间元素,往左移
                     }
                     newArr[i] = arr.shift();//找到新数组元素中比当前元素大的最小元素,用当前元素替换掉该元素。
                 }
             }
             return newArr.length;
         }else {
             throw new Error("the type of param must be Array")
         }
     }
      console.log(lengthOfLIS(arr)) //3
    

    4. 说明

    最后再解释说明一下替换元素的原因。替换元素的目的其实就是给子序列降级。
    比如数组 [4,7,5,1,3,8,6,2]。一眼看上去最长升序子序列是[4,5,8]。不做降级处理的话,假设后面又有一个元素 7。即 [4,7,5,1,3,8,6,2,7] 你的写法很有可能会过滤掉这个 7。而做了降低处理,上面的方法得到的子序列是 [1,2,6]。最后一个元素 7 可以如愿添加进来。成为[1,2,6,7]。长度为 4。正常的升序子序列为 [4,5,6,7],长度也为 4。再强调最后一遍,该题求的是最长子序列长度,子序列长度,子序列长度。不是子序列,不是子序列,不是子序列。当然也可以算出子序列,但是时间复杂度可能会大于 O(n*logn)。

    展开全文
  • 最长升序子序列长度(Python) 源自《挑战程序设计竞赛第二版》,感觉是个有意思的dp所以写这个博客。 题目 请找出(长度为n的数列)的升序子序列的最多是多少。 1<= n <= 1e3 0 <= a_i <= 1e6 输入 第...

    最长升序子序列长度(Python)

    源自《挑战程序设计竞赛第二版》,感觉是个有意思的dp所以写这个博客。

    题目

    请找出(长度为n的数列)的升序子序列的最多是多少。
    1<= n <= 1e3
    0 <= a_i <= 1e6
    输入
    第一行n
    第二行a1,a2,a3,...,ana_1 ,a_2, a_3, ... ,a_n
    输出
    最长升序子序列的长度
    例子
    输入
    5
    4 2 3 1 5
    输出
    3
    因为子序列2,3,5长度为3

    代码

    一个很神奇的dp。时间复杂度O(nlogn)

    import bisect
    #输入
    n = int(input())
    arr = list(map(int,filter(None,input().split(" ")))
    dp = [float("inf") for i in range(n)]
    #dp操作
    for i in arr:
        dp[bisect.bisect_right(dp,i)]=i
    #输出
    print(bisect.bisect_right(dp,1e7))
    
    展开全文
  • java最长升序子序列

    千次阅读 2014-09-28 15:15:25
    最长升序子序列是最长公共子序列的变形。 只要将字符串升序排序后与原字符串求最长公共子序列即可。 以下提供一个工具类可以传入任何形式的数组。(添加新类型的数组时构造方法要自己加)。 package ...

    最长升序子序列是最长公共子序列的变形。

    只要将字符串升序排序后与原字符串求最长公共子序列即可。

    以下提供一个工具类可以传入任何形式的数组。(添加新类型的数组时构造方法要自己加)。

    package com.leejuen.string;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    
    public class LCS
    {
    	private Integer len;
    	private Object str1;
    	private Object str2;
    	LCS(String a,String b)
    	{
    		str1 = a.toCharArray();
    		str2 = b.toCharArray();
    	}
    	LCS(char[] a,char[] b)
    	{
    		str1 = a;
    		str2 = b;
    	}
    	LCS(int[] a,int[] b)
    	{
    		str1 = a;
    		str2 = b;
    	}
    	public int getLCS()
    	{
    		if(len==null) ini();
    		return len;
    	}
    	private void ini()
    	{
    		int str1_len = Array.getLength(str1);
    		int str2_len = Array.getLength(str2);
    		int[][] dp = new int[str1_len+1][str2_len+1];      //初始化dp,java默认数据为0所以不用赋值
    		for(int i=1;i<=str1_len;i++)
    		{
    			for(int j=1;j<=str2_len;j++)
    			{
    				Object tmp1 = Array.get(str1, i-1);
    				Object tmp2 = Array.get(str2, j-1);
    				if(tmp1.equals(tmp2))
    				{
    					dp[i][j] = dp[i-1][j-1]+1;
    				}
    				else
    				{
    					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
    				}
    			}
    		}
    		len = dp[str1_len][str2_len];
    	}
    	//一下是测试:打印4、5
    	/*public static void main(String[] args)
    	{
    		//经典最长公共子序列
    		String a = "BDCABA";
    		String b = "ABCBDAB";
    		System.out.println(new LCS(a,b).getLCS());
    		//最长升序子序列
    		int[] cc1 = {3,1,5,6,2,7,9};
    		int[] cc2 = Arrays.copyOf(cc1, cc1.length);
    		Arrays.sort(cc2);
    		System.out.println(new LCS(cc1,cc2).getLCS());
    	}*/
    }
    


    展开全文
  • 问题描述 给定数组arr,返回arr的最长递增子序列的长度,比如arr=[2,1,5,3,6,4,8,9,7],最长递增子序列为[1,3,4,8,9]返回其...动态规划表,dp[i]表示以arr[i]结尾的最长升序子序列的长度 动态规划表,dpStr[i]表...
  • 给定一个字符串(只包含纯大写字母或者小写字母),在这个字符串中找出最长升序子序列。 例如: 输入:abcdeababca 输出:abcde 二、解法 这个思路是面试官给的:遍历这个字符串,先把所有的升序子字符串放进链表...
  • ACM题解——动态规划系列——最长升序子序列 题目描述 A numeric sequence ofaiis ordered ifa1<a2< ... <aN. Let the subsequence of the given numeric sequence (a1,a2, ...,aN) be any sequence ...
  • 说明:仅仅分享思想和代码设计方法,...最长升序子序列问题 1.1原问题的解:对于一个N个数的升序子序列,假设它为集合B,那B里的元素应该满足是升序的且属于N,且不存在长度比B更长的序列。 1.2 算法:因为要求最...
  • 代码很冗余,没怎么仔细想总之,是一个最长升序子序列的题啦。 #include #include #include #include using namespace std; struct node { char line[25]; int len; int count[27]; }date[11111]; bool...
  • 最长升序子序列一般有两种解法,一种是经典的动态规划方法,复杂度为O(n^2),另外一种方法则借助栈和二分查找,复杂度为O(nlgn)。 动态规划 设d[i]表示以a[i]结尾的最长升序子序列的长度,则可以得到状态转移方程...
  • LIS--最长升序子序列

    2020-03-28 22:49:03
    问题: 第n个最长--》第i个最长,当i = n 成立 状态: maxSum[i] 表示 从第一个元素到第 i 个元素的最长子序列 边界: i == 1 时, maxSum[i] = 1 转移方程: n=1时,maxSum[n] = 1; 选择时:标准a[i] 与 a[j...
  • 动态规划:最长升序子序列

    千次阅读 2015-04-29 11:18:38
    经过分析,发现 “求以ak(k=1, 2, 3…N)为终点的最长上升子序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数,称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样,但是只
  • 方法一:  算法:动规  思路:  如果设立动规状态dp(i)为前i个元素组成的最长上升序列的长度的话,dp... 设立动规状态dp(i)为以第i个元素为结尾的最长上升序列的长度,则dp(i)所代表的序列中,nums[i]是  ...
  • 对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里1 &lt;= i1 &lt; i2 &lt; ... &lt;iK &lt;= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的...
  • 动态规划——最长升序子序列

    千次阅读 2016-11-19 09:58:04
    问题描述 一个数的序列bi,当b1 的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些上升的...比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4,
  • 673. 最长递增子序列的个数 1 public int findNumberOfLIS(int[] nums) { 2 int n=nums.length; 3 if(n==0||n==1)return n; 4 int []dp=new int[n]; 5 int []cnt=new int[n]; ...
  • 给定一个无序的整数序列,找到最长升序子序列的个数。 Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]. 这道题很明显是用...
  • leetCode 最长升序子序列---动态优化

    千次阅读 2018-03-22 23:15:22
    * @file 最长上升子序列.cpp * @Date: 2018/03/22 17:22 * @author: sicaolong * @Contact: sicaolong@163.com * @brief: 思路: 1、memo的状态变换;number[i]与number[j]的大小关系; number[i]&gt;...
  • 动态规划 最长升序子序列

    千次阅读 2014-04-07 21:54:31
    最长升序子序列  http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1299 最长上升子序列 Time Limit: 3000ms Memory limit: 65536K 有疑问?点这里^_^ ...
  • 打印出升序最长的一个子序列,比如这里从1开始到8的序列最长。 这里包含两个问题: 1 找到升序序列序列可以用一个二元组表示 {起始位置,长度},或者{起始位置,终止位置} 或者 {终止位置,长度}。
  • 最长升序子序列 并将最长升序子序列输出
  • 序列变换 Problem Description 我们有一个数列A1,A2…An,你现在要求修改数量最少的元素,使得这个数列严格递增。其中无论是修改前还是修改后,每个元素都必须是整数。 请输出最少需要修改多少个元素。 Input 第一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 424
精华内容 169
关键字:

最长升序子序列