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

    2019-09-30 11:21:39
    定义:一个包含n个数的序列a0, a1, ... , an-1,求序列的最长非降(>=)子序列及其长度。 如:序列5, 3, 4, 9, 6, 8,此最大非降子序列长度为4,子序列为3,4,6,8.(子序列也...要构造最长非降子序列,可知此序列...

    定义:一个包含n个数的序列a0, a1, ... , an-1,求序列的最长非降(>=)子序列及其长度。

    如:序列5, 3, 4, 9, 6, 8,此最大非降子序列长度为4,子序列为3,4,6,8.(子序列也可能不唯一)

     

    运用动态规划,可以构造时间复杂度为O(n2)的算法。

     

    算法基本思路:

    1.打表,获取最长非降子序列的长度;

    要构造最长非降子序列,可知此序列一定是以序列中某个数作为结尾(好像是废话,但就是那样)。

    因此,构造表ml[0...n-1],ml[i] 表示前 i 个数以a[i] 为结尾的最长非降子序列的长度。

    枚举 j (0 <= j < i),若a[j] <= a[i],则a[i]可在以a[j]为结尾的非降子序列后添加,此序列长度为ml[j] + 1.

    因此ml[i] = max(ml[j] + 1) (0 <= j < i) .

    构造出表ml后,遍历ml表,获取最大值。

     

    2.获取最长非降子序列的一个解。

    这个相当简单。只需要在构造表ml的过程中,添加表pre[0...n-1],pre[i] 保存当前a[i]为结尾的非降子序列的前一个元素的编号。

    在获得最长非降子序列的长度后,不断查找表pre即可找到整个序列。(pre 初始化为-1,表示序列的头)

     

    public class LIS{
    
        public static String getMaxLen(int[] a){
            //return the length of longest increasing subsequence and the subsequence
            int[] ml = new int[a.length];
            int[] pre = new int[a.length];
            //build length table
            for(int i = 0; i < ml.length; i ++){
                ml[i] = 1;
                pre[i] = -1;
                for(int j = 0; j < i; j ++){
                    if(a[j] <= a[i] && ml[j] + 1 > ml[i]){
                        ml[i] = ml[j] + 1;
                        pre[i] = j;
                    }
                }
            }
            //find max length
            int k = 0;
            for(int i = 1; i < ml.length; i ++){
                if(ml[k] < ml[i]){
                    k = i;
                }
            }
            String result = Integer.toString(ml[k]);
            String temp = "";
            //get subsequence
            while(k != -1){
                temp = Integer.toString(a[k]) + " " + temp;
                k = pre[k];
            }
            result += "/" + temp;
            return result;
        }
    
        public static void main(String[] args) {
            int[] a = {5, 3, 4, 9, 6, 8};
            String[] result = getMaxLen(a).split("/");
            System.out.println(result[0]);
            System.out.println(result[1]);
        }
        
    }
    Java

     

    转载于:https://www.cnblogs.com/7hat/p/3446049.html

    展开全文
  • 动态规划 最长非降子序列

    问题:
    LIS:longest increasing subsequence
    一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。

    分析:
      首先要定义一个“状态”来代表它的子问题,并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关,而独立于后面的状态。
      假如考虑求A[1],A[2],…,A[i]的最长非降子序列的长度,其中i < N,那么上面的问题变成了原问题的一个子问题(问题规模变小了,你可以让i=1,2,3等来分析)。然后我们定义d(i),表示前i个数中以A[i]结尾的最长非降子序列的长度。如果把d(1)到d(N)都计算出来,那么最终要找的答案就是这里面最大的那个。状态找到了,下一步找出状态转移方程。


    为了方便理解我们是如何找到状态转移方程的,我先把下面的例子提到前面来讲。如果我们要求的这N个数的序列是:
    5,3,4,8,6,7
    根据上面找到的状态,可以得到:(下文的最长非降子序列都用LIS表示)
    ·  前1个数的LIS长度d(1)=1 (序列:5)
    ·  前2个数的LIS长度d(2)=1 (序列:3;3前面没有比3小的)
    ·  前3个数的LIS长度d(3)=2 (序列:3,4;4前面有个比它小的3,所以d(3)=d(2)+1)
    ·  前4个数的LIS长度d(4)=3 (序列:3,4,8;8前面比它小的有3个数,所以d(4)=max{d(1), d(2), d(3)}+1=3)

    分析到这,状态转移方程已经很明显了,如果已经求出了d(1)到d(i-1),那么d(i)可以用下面的状态转移方程得到:
    d(i) = max{1, d(j)+1},其中j < i,A[j] <= A[i]
    所以想要求d(i),就把i前面的各个子序列中,最后一个数不大于A[i]的序列长度加1,然后取出最大的长度即为d(i)。当然了,有可能i前面的各个子序列中最后一个数都大于A[i],那么d(i)=1,即它自身成为一个长度为1的子序列。

    求解

    #include <iostream>    
    #include <algorithm>    
    usingnamespace std;    
    
    int main()    
    {    
        int dp[2000],a[2000],n;    
        while(cin>>n)    
        {    
            memset(dp,0,sizeof(dp));   
    
            int res = 0;    
            for(int i = 0; i < n; i++) cin>>a[i];    
    
            for(int i = 0; i < n; i++)    
            {    
                dp[i] = 1;    
                for(int j = 0; j < i; j++)    
                {    
                    if(a[j] < a[i])    
                        dp[i] = max(dp[i],dp[j] + 1);    
                }    
    
                res = max(res,dp[i]);    
            }    
    
            cout<<res<<endl;    
        }  
    
        return 0;    
    }  

    转自:http://blog.csdn.net/u013445530/article/details/45645307

    展开全文
  • 最长非降子序列以及逆序对数1.最长非降子序列2.逆序对数 1.最长非降子序列 时间复杂度:O(nlogn) 代码: public class 最长非降子序列 { public static void main(String[] args) { int []arr={1,2,5,4,6,4,5...

    最长非降子序列以及逆序对数

    1.最长非降子序列

    时间复杂度:O(nlogn)
    代码:

    public class 最长非降子序列 {
    		public static void main(String[] args) {
    			int []arr={1,2,5,4,6,4,5};
    			int length=lis(arr);
    			System.out.println(length);
    
    				
    		}
    		public static int lis(int[] arr){
    			if (arr==null||arr.length==0) {
    				return 0;
    			}
    			int[] temp =new int[arr.length];
    			temp[0]=arr[0];
    			int len=1;
    			for (int i = 1; i < arr.length; i++) { 
    				int index=lower_bound(temp,len,arr[i]);
    				temp[index]=arr[i];
    				if (index==len) {
    					len++;
    				}
    			}
    			return len;
    		}
    		
    		//二分查找求下界
    		public static int  lower_bound(int []temp,int len,int compare){
    			int low=0;
    			int high=len-1;
    			while (low<=high) {
    				int mid=low+(high-low)/2;
    				if (compare<=temp[mid]) {
    					high=mid-1;
    				}else {
    					low=mid+1;
    				}
    				
    			}
    			return low;
    		}
    }
    
    

    2.逆序对数

    时间复杂度:O(logn)
    代码:

    public class 逆序对个数 {
    		static int count=0;
    		public static void main(String[] args) {
    			int []arr={1,2,5,4,6,3,5,5,5};
    			mergesort(arr, 0,arr.length);
    			System.out.println(count);
    		}
    		public static void mergesort(int []arr,int l,int r){
    			int []c=new int[arr.length];
    			int i,j,temp,mid;
    			if (r>l+1) {
    				mid=l+(r-l)/2;
    				mergesort(arr, l, mid);
    				mergesort(arr, mid, r);
    				temp=l;
    				//利用归并排序
    				for (i = l,j=mid; i < mid&&j<r;) {
    					if (arr[i]>arr[j]) {
    						c[temp++]=arr[j++];
    						count+=mid-i;
    					}else {
    						c[temp++]=arr[i++];
    					}
    				}
    				if (j<r) {
    					for (; j < r; ++j) {
    						c[temp++]=arr[j];
    					}
    				}else {
    					for (; i < mid;++i) {
    						c[temp++]=arr[i];
    					}
    				}
    				for (int k = l; k < r; ++k) {
    					arr[k]=c[k];
    				}
    				
    				
    			}
    			
    		}
    }
    
    展开全文
  • 动态规划——最长非降子序列

    千次阅读 2016-04-20 13:22:57
    动态规划算法求解最长非降子序列问题

    前言

    先分享一篇文章《动态规划:从新手到专家》,作者正是通过这篇文章来学习的。文中对动态规划的设计思想做了非常详细的介绍,并通过简单问题和复杂问题对动态规划的设计流程进行剖析,以下是作者和出处:

    • 作者:Hawstein

    问题描述

    先介绍下问题,给定长度为N的整数序列:A[1], A[2], ......, A[N],求得其中最长非降子序列的长度,即LIS(longest increasing subsequence)。比如如下的整数序列:

    5, 3, 486, 7

    其最大非降子序列即为3, 4, 6, 7,长度为4。

    动态规划求解

    那么如何用动态规划来求解这个问题呢?动态规划中最重要的一部分就是定义状态转移方程,在这个问题中,如果我们定义d[i]为序列A[1], A[2], ..., A[i]的最长非降子序列,但很可惜,在后面思考中,我发现,d[i]和d[i-1]之间很难建立起状态转移关系,A[1]~A[i-1]和A[1]~A[i]二者的最长非降子序列间不一定有公共的部分,如1, 4, 2, 5, 3中前四个整数和前五个整数的最大非降子序列不一定有共同的部分,无法建立起状态转移关系。但如果用d[i]表示以元素A[i]结束的最长非降子序列的长度,那状态方程就有规律可循了,我们以上面的序列为例:

    d(1) = max{1}; //只有5

    d(2) = max{1}; //3之前没有比3小的

    d(3) = max{1, d(2) + 1} = 2; //4之前有3

    d(4) = max{1, d(2) + 1, d(3) + 1} = 3; //8之前有3, 4

    d(5) = max{1, d(2) + 1, d(3) + 1} = 3; //6之前有3, 4

    d(6) = max{1, d(2) + 1, d(3) + 1, d(5) + 1} = 4; //7之前有3, 4, 6

    LIS = max(d[i]) = 4, 1 <= i < = 6

    从上面的流程来看,先求出这个序列中以每个元素作为结尾的最大非降子序列的长度,那问题的解总是以序列中某个元素作为结尾的,所以取最大值即可。而且从上面的公式我们很容易看出求d[i]的过程,简单来说,就是从i往前找,如果某个元素A[j] < = A[i],那么以元素A[j]结尾的最长非降子序列再加上A[i]一定也是一个非降子序列,d[j] + 1肯定是一个非降子序列长度,找到所有符合条件的j,所有符合条件的d[j] + 1的最大值就一定是d[i]的值。从另一个角度去看,因为以A[i]为结尾的最长子序列的倒数第二个元素(假设长度不小于2)肯定是A[i]之前的某一个元素,所有A[j]作为倒数第二个元素的序列就是以A[i]为结尾的子序列。当然,还要考虑特殊的情况,假设A[i]之前没有比其更小的元素,则子序列就是其本身,长度为1。综上所述,状态转移方程如下:

    d[i] = max(1, max(d[j] + 1)), 1 <= j < i, A[j] <= A[i];

    最后问题的解即为:

    LIS = max(d[i]); 1 <= i <= n, n为序列的长度

    文章最后,贴上代码:

    #include <iostream>
    using namespace std;
    
    int LIS(int data[], int n)
    {
        int *d = new int[n];
        int len = 1;
        for(int i = 0; i < n; i++)
        {
            d[i] = 1;
            for(int j = 0; j < i; j++)
            {
                if(data[j] <= data[i])
                {
                    if(d[j] + 1 > d[i])
                    {
                        d[i] = d[j] + 1;
                    }
                }
            }
            if(d[i]>len) len = d[i];
        }
    
        return len;
    }
    
    int main()
    {
        int data[] = {1, 2, 3, 4, 5, 0};
        cout << LIS(data, 6) << endl;
        return 0;
    }
    


    展开全文
  • 最长非降子序列问题:longest increasing subsequence 也叫最长递增子序列 这N个数的序列是: 5,3,4,8,6,7 根据上面找到的状态,我们可以得到:(下文的最长非降子序列都用LIS表示) 前1个数的LIS长度d...
  • 分析来手写一下求取最长非降子序列的过程,用d[i]表示第i个数所对应的最长非降子序列的长度d[0] = 0; d[1] = 1;//5是第一个数,所以只有5这一个数,d[1]=1 d[2] = 1;//因为3之前的所有数都大于3,所以只有3这一个数 d...
  • 动态规划——最长非降子序列的长度题目描述:要求得到一个数组的以非降排列的子序列的最大长度,其中并不要求子序列中的元素一定是按照数组顺序的连续数值。 以6 , 4 , 5 , 8 , 7 , 3 , 9为例,最长非降子序列为{4,...
  • 之前讲到过求最长非降子序列的O(N^2)解法。 链接 这次在原来的基础上介绍一下N*logN解法。 该解法主要是维护一个数组minValue,minValue[i]表示最长上身子序列长度为i的数的最小值。 代码如下: #include <...
  • 最长非降子序列(连续)问题描述: 运行代码: #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N = 1e4; int a[N],b[N]; ...
  • 设dp[i]为以i结尾的最长非降子序列,则dp[i]=max(dp[i],dp[j]+1),其中a[i]>=a[j] 贪心+二分o(nlogn) 用一个新的数组f记录选出的非降子序列,若a[i]>=f[top],则将a[i]插入f,更新top,否则由贪心策略,考虑用a...
  • 最长非降子序列长度
  • 问题分析:如果前i-1个数中的最长非降子序列的最后一个数是ak;那么下一步就是在求前k-1个数中的的最长非降子序列; 因此我们可以设计一个状态opt[j]表示前i个数中用到a[i]所构成的最优解。 那么决策就是在前i-1个...
  • 最长非降子序列 动态规划 java

    千次阅读 2017-02-17 16:18:40
    给定一个由n个正整数组成的序列,从该序列中删除若干个整数,使剩下的整数组成非降子序列,求最长非降子序列。 例如,由12个正整数组成的序列为: 48,16,45,47,52,46,36,28,46,69,14,42 请在序列中...
  • 动态规划——最长非降子序列数组

    千次阅读 2014-09-19 09:28:27
    让我们沿用“入门”一节里那道简单题的思路来一...假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度,其中i,那么上面的问题变成了原问题的一个子问题(问题规模变小了,你可以让i=1,2,3等来分析) 然后我们
  • 思路:首先会想到求得是最长非降子序列的个数,那么如何实现,似乎没有足够巧妙地方案,细心观察数据就能得出这样的结论:先对l按从小到大的顺序 排序,然后得到的序列中w的最长递减子序列的长度就是答案。...
  • 问题大致是给出一组数列,求出数列中最长降子序列或者最长不升子序列,这里的子序列在原序列中可以不连续。  顾名思义,不降可理解为递增,不升亦可解释为递减。  显而易见,动态规划是一种容易让人想到的...
  • 一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度 思路分析 这是博客http://hawstein.com/posts/dp-novice-to-advanced.html 上的第二个例子 编写代码 递归的代码看起啦更加好理解一些,不过...
  • 最长非降子序列LIS

    2019-03-03 18:43:00
    任何一个需要用dp解决的问题,都有一个状态转移方程,当前问题的解由上一个子问题推出 而LIS问题的状态转移方程为: dp[i]=max{dp[i], dp[j]+1} 边界条件:dp[i] = 1 (i=1~n) 限制条件:j<i, a[j] <= a...
  • 最长非降子序列模型

    千次阅读 2014-04-16 21:28:43
    1)首先最长单调子序列(一维) 描述: 给定一整型数列{a1,a2...,an}(0 如:1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13,长度为5。 题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=17...
  • 最长非降子序列。 例如,由12个正整数组成的序列为: 48,16,45,47,52,46,36,28,46,69,14,42 请在序列中删除若干项,使剩下的项为非降(即后面的项不小于前面的项)序列,剩下的非降序列 最多为多少项? ...
  • 转载来自: http://hawstein.com/posts/dp-novice-to-advanced.html ... ...一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS:longest increasing subseq
  • 这次我们来讲解一个叫做“最长非下降子序列”的问题及他的O(n^2)解法。 首先我们来描述一下什么是“最长非下降子序列”。 给你一个长度为n的数组a,在数组a中顺序找到最多的元素(这些元素的顺序不能乱,但是可以不...
  • 用于求上升序列 int ask( int x) // 返回最后一个 小于等于x 的数的位置 { int pos= 0 ; while (x) pos =max(pos,f[x]),x-= lowbit(x); return pos; } void add( int x, int pos) { while (x...
  • #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n, x; vector<int> v, vec; cin >> n; for (int i = 0; i &l...
  • 最长非降子序列的长度问题 先给出问题: 比如现在有一组数,5,3,4,2,7,答案显然是3,序列是3,4,7 设计要素 1.问题建模,获得优化的目标函数。 2.划分子问题。 3.得到问题最优函数值与子问题的最优函...

空空如也

空空如也

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

最长非降子序列