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

    千次阅读 2015-12-13 22:28:35
    什么是最长有序子序列呢? 首先要明白子序列和子串不同,可以不连续,然后保证有序就是有序子序列了。 比如有如下数组: I 0 1 2 3 4 5 6 7 8 Num[I] 1 4 7 2 5 8

    什么是最长有序子序列呢?

    首先要明白子序列和子串不同,可以不连续,然后保证有序就是有序子序列了。

     
    

    比如有如下数组:

    I

    0

    1

    2

    3

    4

    5

    6

    7

    8

    Num[I]

    1

    4

    7

    2

    5

    8

    3

    6

    9

    F[I]                            

    1

    2

    3

    2

    3

    4

    3

    4

    5

    其中F[I]存的是以NUM[I]结尾的子序列的最长长度。

    上面看懂了,求一个数组的最长有序子序列就容易了,代码如下:

    public class Test {
        public static void main(String[] args) {
            int[] num = new int[]{1,4,7,2,5,8,3,6,9};
            int[] f = new int[num.length];
            for (int i = 0;i < num.length;i++) {
                f[i] = 1;
            }
            int max = f[0];
            for (int i = 1;i < num.length;i++) {
                for (int j = 0;j < i;j++) {
                    //更新条件,1是有序,2是长度能变长
                    if (num[i] >= num[j] && f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        if (f[i] > max) {
                            max = f[i];//更新最长的长度
                        }
                    }
                }
            }
            System.out.println(max);
        }
    }
    






    展开全文
  • 主要介绍了C语言实现最长递增子序列问题的解决方法,采用递归的方法解决该问题,是非常经典的一类算法,需要的朋友可以参考下
  • //算法8.10 相邻两个有序子序列的归并 #include <stdio.h> #include<stdlib.h> #define MAXSIZE 20 //顺序表的最大长度 typedef struct { int key; char *otherinfo; }RedType; ...

    此代码可以正常运行,下附有运行区

    //算法8.10 相邻两个有序子序列的归并
    #include <stdio.h>
    #include<stdlib.h>
    #define  MAXSIZE  20          						//顺序表的最大长度
    typedef struct
    {
    	int key;
    	char *otherinfo;
    }RedType;
    																		
    void Create_Sq(RedType *R)
    {
    	int i,n;
    	printf("请输入数据个数,不超过%d个\n",MAXSIZE);
    	scanf("%d",&n);										//输入个数
    	printf("请输入待合并的数据:\n");
    	while(n>MAXSIZE)
    	{
    		printf("个数超过上限,不能超过%d个,请重新输入\n",MAXSIZE);
    		scanf("%d",&n);
    	}
    	for(i=0;i<n;i++)
    		scanf("%d",&R[i].key);
    }
    
    void Merge(RedType R[],RedType T[],int low,int mid,int high)
    { 
       //将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high] 
    	int i,j,k;
    	i=low; j=mid+1;k=low; 
        while(i<=mid&&j<=high)
    	{                 	
    		//将R中记录由小到大地并入T中 
    		if(R[i].key<=R[j].key) T[k++]=R[i++]; 
            else T[k++]=R[j++]; 
    	} 
    	while(i<=mid)                            		//将剩余的R[low..mid]复制到T中 
    		T[k++]=R[i++];                 
    	while(j<=high)                           		//将剩余的R[j.high]复制到T中 
    		T[k++]=R[j++];                       
    }//Merge 
    void show(RedType *T,int low,int high)
    {
    	int i;
    	for(i=low;i<=high;i++)
    		printf("%d ",T[i].key);
    	printf("\n");
    }
    void main()
    {
    	RedType *R=new RedType[MAXSIZE];
    	RedType *T=new RedType[MAXSIZE];
    	Create_Sq(R);
    	int low,mid,high;
    	printf("请输入第一个有序子序列的起点、终点下标和第二个有序子序列的终点下标:\n");
    	scanf("%d %d %d",&low,&mid,&high);
    	Merge(R,T,low,mid,high);
    	printf("合并后的结果为:\n");
    	show(T,low,high);
    }
    

    在这里插入图片描述

    展开全文
  • 求最长有序子序列长度

    千次阅读 2013-11-25 23:22:05
    两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a 输入: 一连串英文小写字母,长度不超过15,保证最开始的状态不是一个严格单增的序列。 输出:1表示甲可以赢,0...

    public class Test {
    	
    	public static void who(String in){
    		char[] ch=in.toCharArray();
    		int[] arr=new int[ch.length];
    		for(int i=0;i<ch.length;i++){
    			arr[i]=(int)ch[i];
    		}
    		int maxlenth=getMaxOrder(arr);
    		System.out.println(maxlenth);
    	}
    
    	public static int getMaxOrder(int[] L)
    	{
    	    int n = L.length;
    	    float[] B = new float[n+1];//数组B;
    	    B[0]=-10000;//把B[0]设为最小,假设任何输入都大于-10000;
    	    B[1]=L[0];//初始时,最大递增子序列长度为1的最末元素为a1
    	    int len = 1;//Len为当前最大递增子序列长度,初始化为1;
    	    int p,r,m;//p,r,m分别为二分查找的上界,下界和中点;
    	    for(int i = 1;i<n;i++)
    	    {
    	        p=0;r=len;
    	        while(p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列;
    	        {
    	           m = (p+r)/2;
    	           if(B[m]<L[i]) p = m+1;
    	           else r = m-1;
    	        }
    	        B[p] = L[i];//将长度为p的最大递增子序列的当前最末元素置为ai+1;
    	        if(p>len) len++;//更新当前最大递增子序列长度;
    	    }
    	    return len;
    	}
    	
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		String str="aaa";
    		who(str);
    	}
    
    }
    


    展开全文
  • 1.求最长递增子序列长度 方法一:动态规划O(n2) public static int findLongest2(int[] A) { int n = A.length; int[] f = new int[n];// 用于存放f(i)值; f[0] = 1;// 以第a1为末元素的最长递增子序列...

    1.求最长递增子序列长度

    方法一:动态规划O(n2) 

    dp[i]:以i结尾的最长递增子序列

    初始化:dp[*]=1

    公式:dp[i]=max(dp[j]+1) and nums[i] > nums[j],0<=j<i

    结果:max(dp)

    public static int findLongest2(int[] A) {
    		int n = A.length;
    		int[] f = new int[n];// 用于存放f(i)值;
    		f[0] = 1;// 以第a1为末元素的最长递增子序列长度为1;
    		int maxLen = Integer.MIN_VALUE;
    		for (int i = 1; i < n; i++)// 循环n-1次
    		{
    			f[i] = 1;// f[i]的最小值为1;
    			for (int j = 0; j < i; j++)// 循环i 次
    			{
    				if (A[j] < A[i] && f[j] +1 > f[i]) {
    					f[i] = f[j] + 1;// 更新f[i]的值。
    					maxLen = Math.max(maxLen, f[i]);
    				}
    			}
    		}
    
    		return maxLen;
    	}

    方法二:O(nlogn)

    思路:

    例子:假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7,可以看出来它的LIS长度为5。
    定义一个序列B,与的d同大小。
    此外,我们用一个变量Len来记录现在最长算到多少了
    首先,把d[1]有序地放到B里,令B[1] = 2,就是说当只有1一个数字2的时候,长度为1的LIS的最小末尾是2。这时Len=1
    然后,把d[2]有序地放到B里,令B[1] = 1,就是说长度为1的LIS的最小末尾是1,d[1]=2已经没用了,很容易理解吧。这时Len=1
    接着,d[3] = 5,d[3]>B[1],d[3]=5,就是说长度为2的LIS的最小末尾是5,很容易理解吧。这时候B[1..2] = 1, 5,Len=2
    再来,d[4] = 3,它正好加在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是1,这样很容易推知,长度为2的LIS最小末尾是3,于是可以把5淘汰掉,这时候B[1..2] = 1, 3,Len = 2
    继续,d[5] = 6,它在3后面,因为B[2] = 3, 而6在3后面,于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6,还是很容易理解吧? Len = 3 了。
    第6个, d[6] = 4,你看它在3和6之间,于是我们就可以把6替换掉,得到B[3] = 4。B[1..3] = 1, 3, 4, Len继续等于3
    第7个, d[7] = 8,它很大,比4大,嗯。于是B[4] = 8。Len变成4了
    第8个, d[8] = 9,得到B[5] = 9,嗯。Len继续增大,到5了。
    最后一个, d[9] = 7,它在B[3] = 4和B[4] = 8之间,所以我们知道,最新的B[4] =7,B[1..5] = 1, 3, 4, 7, 9,Len = 5。

    java代码如下:

    public static int findLongest(int[] A) {
    		int n = A.length;
    		int[] B = new int[n + 1];
    		B[1] = A[0];
    		int len = 1,index;
    		for (int i = 1; i < n; i++) {
    			if (A[i] > B[len]) {
    				len++;
    				B[len] = A[i];
    			} else {
    				index = search(1, len, B, A[i]);
    				B[index] = A[i];
    			}
    		}
    		return len;
    	}
    // 二分查找,查找第一个比他大的数
    	public static int search(int start, int end, int[] a, int target) {
    		int mid;
    		while (start < end) {
    			mid = (start + end) / 2;
    			if (target >= a[mid])
    				start = mid + 1;
    			else
    				end = mid;
    		}
    		return start;
    	}

    python代码比较简单,如下:

    from bisect import bisect_left
    
    def lengthOfLIS(nums: List[int]) -> int:
        dp = []
        for x in nums:
            if not dp or x > dp[-1]:
                dp.append(x)
            else:
                dp[bisect_left(dp, x)] = x
        return len(dp)

    2.打印最长递增子序列

    方法一:打印第一个最长子序列O(n2) 

    输入例子:

    7

    89 256 78 1 46 78 8

    数组array    ai8925678146788
    长度list    len(ai)1211232
    // 打印第一个最长序列
    	public static ArrayList<Integer> maxSubIncreaseArray(int[] array) {
    		int n = array.length;
    		int[] list = new int[n];//存储每个数结尾的最长串
    		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();// 存储所有递增序列
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		int index = -1;// 用于标记当前元素之前的第一个递增子序列的位置
    		int maxIndex = 0;// 用于标记该序列的最长递增子序列的位置
    		int max = Integer.MIN_VALUE;// 最长递增子序列的长度
    		list[0] = 1;// 该列表用于标记包括当前元素在内的前半部分的最长递增子序列的长度
    		tmp.add(array[0]);
    		res.add(tmp);
    		for (int i = 1; i < n; i++) {
    			index = -1;
    			tmp = new ArrayList<Integer>();
    			for (int j = 0; j < i; j++) {
    				if (array[j] < array[i] && list[j]+1 > list[i]) {
    					list[i] = list[j]+1;
    					index = j;
    				}
    			}
    			if (index > -1)
    				tmp.addAll(res.get(index));
    			tmp.add(array[i]);
    			res.add(tmp);
    			if (list[i] > max) {
    				max = list[i];
    				maxIndex = i;
    			}
    		}
    		return res.get(maxIndex);
    	}

    方法二:打印最后一个最长字符串O(nlogn),在求长度的方法上,与上述方法相结合

    	public static int findLongest(int[] A) {
    		int n = A.length;
    		int[] B = new int[n + 1];
    		int[] C = new int[n + 1];//存储i长的字符串位置
    		C[1] = 1;
    		B[1] = A[0];
    		int len = 1, mid;
    
    		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();// 存储所有递增序列
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		int index = -1;// 用于标记当前元素之前的第一个递增子序列的位置
    		int maxIndex = 1;// 用于标记该序列的最长递增子序列的位置
    		int max = Integer.MIN_VALUE;// 最长递增子序列的长度
    		tmp.add(A[0]);
    		res.add(new ArrayList<Integer>());
    		res.add(tmp);
    
    		for (int i = 1; i < n; i++) {
    			tmp = new ArrayList<Integer>();
    			if (A[i] > B[len]) {
    				len++;
    				B[len] = A[i];
    				C[len] = i + 1;
    				tmp.addAll(res.get(C[len - 1]));
    				tmp.add(A[i]);
    				if (len > max) {
    					max = len;
    					maxIndex = i + 1;
    				}
    			} else {
    
    				index = search(1, len, B, A[i]);
    				B[index] = A[i];
    				while (index > 0 && B[index] >= A[i]) {
    					index--;
    				}
    				if (index > 0) {
    					tmp.addAll(res.get(C[index]));
    					C[index + 1] = res.size();
    				} else {
    					C[1] = res.size();
    				}
    				tmp.add(A[i]);
    
    			}
    			res.add(tmp);
    		}
    		// 打印最后一个最长序列
    		System.out.println(res.get(maxIndex));
    		return len;
    	}

    3. 和最大的递增子序列的和

    // 和最大的递增子序列
    	public static long SubLongestAscendSum(int[] a) {
    		int n = a.length;
    		int f[] = new int[n];
    		f[0] = a[0];
    		long max = f[0];
    
    		for (int i = 1; i < a.length; i++) {
    			f[i] = a[i];
    			for (int j = 0; j < i; j++) {
    				if (a[j] < a[i] && f[j] + a[i] > f[i]) {
    					f[i] = f[j] + a[i];
    					max = Math.max(f[i], max);
    				}
    			}
    		}
    		return max;
    	}

    4. 打印和最大的递增子序列的和

    // 打印和最大的递增子序列
    	public static List<Integer> SubLongestAscendSum2(int[] a) {
    		int n = a.length;
    		int f[] = new int[n];
    		f[0] = a[0];
    		long max = f[0];
    		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();// 存储所有递增序列
    		ArrayList<Integer> tmp = new ArrayList<Integer>();
    		int index = -1;// 用于标记当前元素之前的第一个递增子序列的位置
    		int maxIndex = 0;// 用于标记该序列的最长递增子序列的位置
    		tmp.add(a[0]);
    		res.add(tmp);
    
    		for (int i = 1; i < a.length; i++) {
    			f[i] = a[i];
    			index = -1;
    			tmp = new ArrayList<Integer>();
    			for (int j = 0; j < i; j++) {
    				if (a[j] < a[i] && f[j] + a[i] > f[i]) {
    					f[i] = f[j] + a[i];
    					index = j;
    				}
    			}
    			if (index > -1)
    				tmp.addAll(res.get(index));
    			tmp.add(a[i]);
    			res.add(tmp);
    			if (max < f[i]) {
    				max = f[i];
    				maxIndex = i;
    			}
    		}
    		return res.get(maxIndex);
    	}

     

     

    展开全文
  • 最长有序子序列—动态规划算法

    千次阅读 2012-08-18 22:38:39
    计算f[i]时,f[i]=max(f[j]+1) ,(其中,a[i]>a[j],i>j>=0),意思是以a[i]为结尾,找出在a[i]前比a[i]小的数据中以该数据为结尾的最大有序子序列长度max(f[j]),则以a[i]结尾的最大有序子序列长度为max(f[j ...
  • 数组最大连续子序列

    千次阅读 2018-09-04 14:11:12
    题目:给定一个数组,其中元素可正可负,求其中最大连续子序列的和。 这题是一道非常经典的面试题,会经常出现在各种面试中,具体有好几种不同时间复杂度的解法,那么最好的方法是用动态规划方法来求解。 第一种:...
  • 最长递增子序列LIS 问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8}...
  • 应该把这个问题看成一个基本问题,感觉用动态规划的算法比较容易想到,也很不错,关于那个改进的O(nlogn)的算法有些不太明白,大部分动态规划都要寻求一个当前状态的最小值或最大值,...最长递增子序列问题是一个很...
  • 分析:指定两个指针,point1为哨兵,point2来动态查询最长序列 代码 public class Main { public static void main(String[] args) { int[] a = {1,6,8,3,2,0,61}; int max = 1; int point1 = 0; ...
  • 最长有序子序列的C++实现代码

    千次阅读 2011-09-02 21:31:51
    本题用普通动态规划求解,递推式为:f[i]=max{f[j]+1,a[i][j]},f[i]表示以a[i]结尾的最长递减子序列的长度。初始条件f[i]=1,1,通过枚举i,j,可求出问题的解,解为max{f[i],1。复杂度O(n^2)。 #include ...
  • hdu1160--最长有序子序列

    千次阅读 2013-05-28 23:34:46
    算法原理: 数组a[]为待处理数组 f[]用于记录a[]数组中,以对应位置数据为结尾的最长有序序列长度...以a[]={1,4,7,2,5,8,3,6,9},计算最长递增有序子序列为例 初始化f[]={1, 1, 1, 1, 1, 1, 1,1,1},p[]={0,1,2,3,4,5,6
  • 最长连续递增子序列题目答案注意 题目 答案 #include<stdio.h> int main() { int n; scanf("%d",&n); int a[n],i; for(i=0;i<n;i++) scanf("%d",&a[i]); int count=0,max=0,flag=0,...
  • 最长上升子序列 (LIS) 详解+例题模板 (全)

    万次阅读 多人点赞 2018-07-25 20:45:49
    所有的d(i)里面最大的那个就是最长上升子序列。其实说的通俗点,就是每次都向前找比它小的数和比它大的数的位置,将第一个比它大的替换掉,这样操作虽然LIS序列的具体数字可能会变,但是很明显LIS长度还是不变的,...
  • LIS 最长递增子序列 Java实现

    千次阅读 2015-08-09 20:51:53
    最长递增子序列 LIS java实现
  • 【前言】动态规划:与分治法相似,即通过组合问题来求解原问题,不同的是分治法是将问题划分为互不相交的问题,递归求解问题,再将他们组合起来求出原问题的解。 动态规划则应用于问题重叠的情况,通常用来...
  • 用java实现 最长连续递增子序列

    千次阅读 2019-03-10 20:09:14
    7-52最长连续递增子序列(20 分) 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n...
  • 最长递增子序列之动态规划(C语言实现)

    千次阅读 多人点赞 2020-05-10 23:30:00
    (1)设置一个mark[]数组,mark[]数组的个数和原序列data[]的个数相等,mark[i]表示以data[i]作为结尾的最长递增子序列的长度; (2)在确定mark[i]时,在0到i-1中找到这样一个k,使得data[k]<data[i]且mark[k]=...
  • 最长上升子序列 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的...
  • 主要解题思路:求解dp[i],表示以arr[i]这个数结尾的情况下, 最长递增子序列的长度. O(N*N)的做法:源码 O(N* logN)的解法, 求解dp[i],源码 /*** * 1. 增加辅助数组 ends[b]和right 变量。 * 2. ends[b]...
  • 习题3.4最长连续递增子序列(20分) 给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数...
  • 给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。 题目分析 这时一个很典型的动态规划题目,数组不一定是有序的,而且连续子序列中的符号也不一定一致,这是两点需要注意的,...
  • 动态规划之子序列问题

    千次阅读 2020-06-06 23:31:35
    最长递增子序列I 题目描述 给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数N。 第二行包含N个整数,表示完整序列。 输出格式 输出一个整数,表示最大长度。 数据范围...
  • 最长递增子序列的三种算法

    万次阅读 多人点赞 2018-07-25 15:34:12
    最长递增子序列   问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8}...
  • 方法一:dp,对应原序列的每个元素,dp数组记录包含这个数在内的与之前所有数一起能构成的最长有序子序列的长度,最后对dp数组遍历取最大值即可   #include #include #include #include using namespace std;...
  • python实现最长连续递增子序列

    千次阅读 2020-07-14 10:03:59
    给定一个没有排序的整数数组,找到最长的连续递增的子序列(子数组)的长度 注意审题:该题求的是连续,故可以使用滑动窗口的方法来求解 def findlcis(alist): n=o res=0 for i in range(alist): if alist[i]&...
  • 按照数据结构来划分的话,最长上升子序列(LIS)是属于线性DP,其作为动态规划经典入门模型,重要性也是不言而喻的。而LIS问题也有很多种变型,对于这些问题有的超过了动态规划的适用范围,有的需要对转移方程进行更改...
  • 找出一个数组中最长连续递增子序列(部分有序),例如: (1, 9 , 2 , 5 , 7 , 3 , 4 , 6, 8,0, )中递增的子序列有:(1,9)、(2,5)、(5,7)、(3,4,6,8)则最长的递增子序列 为(3, 4, 6, 8) import java.util....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 75,420
精华内容 30,168
关键字:

最大有序子序列