求最长有序子序列长度

矫情吗；* 2022-09-18 12:52 189阅读 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);
    	}
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关经典算法——求最长公共子序列的长度

1 include <cstdio> 2 include <iostream> 3 4 using namespace std;

╰+攻爆jí腚メ/ 2023年07月12日 05:05/ 0 赞/ 27 阅读

相关求最长有序子序列长度

public class Test { public static void who(String in){ char[]

矫情吗；*/ 2022年09月18日 12:52/ 0 赞/ 190 阅读

相关判断子序列、求最长公共子序列算法实现

include<stdio.h> include<string.h> include<stdlib.h> define FAIL 0

电玩女神/ 2022年08月12日 06:29/ 0 赞/ 235 阅读

相关动态规划：求最长公共子串/最长公共子序列

最长公共子序列和最长公共子串区别最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence

我不是女神ヾ/ 2022年08月08日 03:24/ 0 赞/ 297 阅读

相关求最长公共子序列

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列

亦凉/ 2022年08月04日 04:26/ 0 赞/ 194 阅读

相关求最长公共子序列（LCS）

题目：求最长公共子序列（LCS）思路：经典的动态规划法， c\[i,j\]表示Xi与Yj的最长公共子序列，其中 Xi = \{x1，、、、xi\}

傷城~/ 2022年05月30日 02:59/ 0 赞/ 211 阅读

相关求最长素子串的长度

本来在leetcode里面搜的是哈系表相关算法练习,把这个题做完后,感觉没用到相关知识\[哭笑一波 ?\] > 给定一个字符串，请你找出其中不含有重复字符的最长子串的

﹏ヽ暗。殇╰゛Y/ 2022年03月22日 07:29/ 0 赞/ 221 阅读

相关求最长公共子序列（动态规划）

求最长公共子序列（动态规划）首先弄清楚，最长公共子串与最长公共子序列的区别：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。比如说：A=\{

た入场券/ 2022年01月26日 03:11/ 0 赞/ 295 阅读

相关求数组中最长递增子序列

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] [http://www.blogjava.net/dongwq/archive/200

妖狐艹你老母/ 2022年01月15日 10:07/ 0 赞/ 225 阅读

相关求数组中最长递增子序列的长度

求数组中最长递增子序列的长度什么是最长递增子序列呢? 问题描述如下: 设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Li

浅浅的花香味﹌/ 2021年12月04日 06:05/ 0 赞/ 289 阅读