最长单调递增子序列的长度问题
所谓子序列,就是在原序列里删掉若干个元素后剩下的序列,以字符串"abcdefg"为例子,去掉bde得到子序列"acfg",。现在的问题是,给你一个数字序列,你要求出它最长的单调递增子序列的长度(LIS)。
设给定序列为 array[],大小为 n, 最长单调子序列必定以序列array[]中的某一个元素结尾,这是废话。
设lis[i]为以array[i]结尾的最长单调子序列的长度,那么array[]的LIS的长度就是
max{lis[i]} (0<=i<n)
显然此问题具有最优子结构性质:
lis[0]=1;
lis[i+1]=max{1,lis[k]+1} (array[i+1]>array[k], k <= i)
即如果array[i+1]大于array[k],那么第i+1个元素可以接在lis[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。
import java.util.Scanner;
public class TestLIS{
private int n;
private int array[];
private int lis[];
public TestLIS(int n,int[] array){
this.n=n;
this.array=array;
lis=new int[n];
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] array=new int[n];
for(int i=0;i<n;i++){
array[i]=in.nextInt();
}
TestLIS tl=new TestLIS(n,array);
int maxl=tl.lis();
System.out.println("最长单调递增子序列长度:"+maxl);
System.out.println();
System.out.println("最长单调递增子序列构成");
int k=tl.max();
tl.print(k);
System.out.println();
}
//求数组最长递增子序列
public int lis()
{
for(int i =0;i< n;i++)
{
lis[i]=1;
for(int j=0;j< i;j++)
{
if(array[j]< array[i]&&(lis[j]+1>lis[i]))
lis[i]=lis[j]+1;
}
}
int max=0;
for(int k=0;k< lis.length;k++)
{
if(lis[k]>max)
max=lis[k];
}
return max;
}
//求数组中最大值下标
private int max()
{
int max = lis[0];
int k = 0;
for (int i = 0; i < lis.length; i++)
{
if (max < lis[i])
{
max = lis[i];
k = i;
}
}
return k;
}
//输出
public void print(int k)
{
for (int i = k - 1; i >= 0; i--)
{
if (lis[k] == lis[i] + 1 && array[i] <= array[k])
{
print(i);
break;
}
}
System.out.print(array[k] + " ");
}
}
运行:
5
1 10 4 9 7
最长单调递增子序列长度:3
最长单调递增子序列构成
1 4 9
下载:
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1691677
NULL 博文链接:https://128kj.iteye.com/blog/1688560
NULL 博文链接:https://128kj.iteye.com/blog/1688982
NULL 博文链接:https://128kj.iteye.com/blog/1689359
NULL 博文链接:https://128kj.iteye.com/blog/1689243
NULL 博文链接:https://128kj.iteye.com/blog/1688360
NULL 博文链接:https://128kj.iteye.com/blog/1689477
NULL 博文链接:https://128kj.iteye.com/blog/1688531
基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf
这些算法按照难度和类型进行分类,包括数组、字符串、递归、排序、搜索、动态规划等多个领域。每个算法都提供了详细的解析和代码实现,帮助读者深入理解算法的原理和应用。 对于初学者,这些算法可以帮助他们掌握...
每个案例都是经过精心筛选的,具有代表性和实用性,是算法学习和实践的绝佳素材。 每个案例都配有详细的解析和注释,包括算法思路、实现代码和复杂度分析,帮助读者深入理解算法的实现细节和时间空间复杂度,并掌握...
这本书包含了各种经典的算法问题,涵盖了排序、查找、递归、动态规划、图论等多个领域,每个案例都经过精心挑选,具有代表性和实用性,是C语言算法学习的绝佳素材。 每个案例都配有详细的解析和注释,包括算法思路...
PID控制算法应用讲解,另外还包含了自动驾驶学习资料的获取: 涵盖感知,规划和控制,ADAS,传感器; 1. apollo相关的技术教程和文档; 2.adas(高级辅助驾驶)算法设计(例如AEB,ACC,LKA等) 3.自动驾驶鼻祖...
算法系列15天速成——第一天 七大经典排序【上】 算法洗脑系列(8)算法洗脑系列(8篇)——第八篇 概率思想 算法洗脑系列(8篇)——第七篇 动态规划 算法洗脑系列(8篇)——第六篇 回溯思想 算法洗脑系列(8篇)...
1 6 5 动态规划算法 20 1 6 6 用整数编码集合 21 1 6 7 二分查找 23 1 7 建议 25 1 8 走得更远 27 第 2 章 字符串 28 2 1 易位构词 28 2 2 T9:9 个按键上的文字 29 2 3 使用字典树进行拼写纠正 31 2 4 KMP(Knuth-...
1规划、二次规划、拉格朗曰法、起作用集算法、路径跟踪法、粒子群优化算法、基本粒子群算法、带压缩因子的粒子群算法、权重改进的粒子群算法、线性递减权重法、自适应权重法、随机权重法、变学习因子的粒子群算法、...
蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例 基于人工蚁群优化的矢量量化码书设计算法 具有自适应杂交特征的蚁群算法 蚁群算法在原料矿粉混匀优化中的应用 基于多Agent的蚁群算法在车间动态调度中的...
针对装备精确保障任务规划中任务时序逻辑约束和资源占用冲突等问题,建立以时效优先为目标的数学模型,提出基于多维动态列表规划和混沌蝙蝠算法的混合任务规划方法.通过多维动态列表规划选择处理的任务,设计具有自适应...
以平面随机梅花桩为例,设定随机起始点与目标区域,利用深度强化学习算法进行训练,并得到六足机器人在平面梅花桩环境中的运动策略。为了加快训练进程,采用具有优先经验重放机制的深度确定性策略梯度算法。最后在...