Java实现求数组最长子序列算法示例
作者:antchow- 发布时间:2023-09-28 12:35:14
标签:Java,数组,最长子序列,算法
本文实例讲述了Java实现求数组最长子序列算法。分享给大家供大家参考,具体如下:
问题:给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6。
思路1:第一眼看到题目,很多人肯定第一时间想到的是LCS。先给数组排个序形成新数组,然后再把新数组和原数组拿来求LCS,即可得到答案。这种解法很多人能想得到,所以就不再赘述。
思路2:按照思路1的想法,最后求LCS时还是得用到DP,我们干嘛不直接用DP来求解呢。对于数组arr,我们从后往前遍历数组,分别求出当子序列以arr[i]
结尾时的最长子序列,然后取其中的最大值。即可得到整个数组的最长子序列。 那么怎么求以arr[i]
结尾时的最长子序列呢,这就转换成一个DP问题了。要求arr[i]
的最长子序列,只需要求出arr[i-1]
的最长子序列。即:max{arr[i]}=max{arr[i-1]}+1
。
java实现代码:
public class arrDemo {
public static void main(String[] args) {
// int[] arr = {89, 256, 78, 1, 46, 78, 8};
int[] arr = { 1, 3, 5, 2, 4, 6, 7, 8 };
// int[] arr = {6, 4, 8, 2, 17};
int max = 0;
int maxLen = arr.length;
// 从后往前遍历数组,分别求出以arr[i]结尾的时候的最长子序列长度
for (int i = arr.length - 1; i > 0; i--) {
int[] newArr = new int[i];
System.arraycopy(arr, 0, newArr, 0, i);
int currentLength = 1 + dp(newArr, arr[i]);
if (currentLength > max)
max = currentLength;
// 最长子序列的长度最长为原始数组的长度,
// 因为不需要我们求最长子序列的元素,所以直接结束循环,减少时间开销
if (max == maxLen)
break;
}
System.out.println(max);
}
public static int dp(int[] arr, int end) {
// 递归结束条件
if (arr.length == 1) {
// 小于end则包含在子序列中,子序列长度+1
if (arr[0] <= end)
return 1;
else
return 0;
}
// 遍历数组,找到最靠近end的并且<=end的元素位置i
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] <= end) {
// 从i处截断数组,将arr[0]到arr[i-1]组成新数组继续递归求长度
int[] newArr = new int[i];
System.arraycopy(arr, 0, newArr, 0, i);
// 分别计算包含arr[i]时的最长子序列和不包含arr[i]时的最长子序列,取最大值
int containLen = dp(newArr, arr[i]) + 1;
int notContainLen = dp(newArr, end);
return containLen > notContainLen ? containLen : notContainLen;
}
}
// 如果没找到比end更小的,返回长度为0
return 0;
}
}
运行结果:
6
我的方法由于中间开辟了多个新数组,可能占用的空间有点多,不过我觉得应该也不是很多- -,具体我也没统计过。如果有不对的地方还请指正。
希望本文所述对大家java程序设计有所帮助。
来源:https://blog.csdn.net/ztzy520/article/details/78018321
0
投稿
猜你喜欢
- 详解 Java中日期数据类型的处理之格式转换的实例概要:日期以及时间格式处理,在Java中时间格式一般会涉及到的数据类型包括Calendar
- 这篇文章主要介绍了Java如何实现支付宝电脑支付基于servlet版本,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学
- 写在最前端1.SpringAOP中共有六种通知类型,只要我们自定义一个类实现对应的接口,它们全都是org.springframework.a
- 本文实例为大家分享了Java实现酒店客房管理系统的具体代码,供大家参考,具体内容如下LoginFrame.javapackage login
- 前言最近看了内部类后,总结一下,首先内部类嵌套在其他内部的类,根据出现的位置和关键字,可以分为以下四种类:成员内部类,静态内部类,方法内部类
- 如今,企业级应用程序的常见场景是同时支持HTTP和HTTPS两种协议,这篇文章考虑如何让Spring Boot应用程序同时支持HTTP和HT
- 目录一、数组、集合和 LINQ1、数组二、字符串内插三、模式匹配四、委托和 Lambda 表达式五、async/await六、属性一、数组、
- 一、创建Config配置中心项目1.添加依赖 <dependency> <groupId>org.sp
- 目录前言一、Spring Boot对Redis的支持二、实战1、添加依赖2、redis配置3、实现序列化4、创建Redis连接工厂,同时注册
- 本文实例为大家分享了java实现图片分割指定大小的具体代码,供大家参考,具体内容如下1.使用工具:ThumbnailsThumbnails
- 话不多说,请看下面//C# 代码int year = DateTime.Now.Year;int month = DateTime.Now.
- 背景传说里玉皇大帝派龙王马上降雨到共光一带,龙王接到玉皇大帝命令,立马从海上调水,跑去共光施云布雨,但粗心又着急的龙王不小心把海里的鲸鱼随着
- 在 Java 中将 Object 转换为 Int我们可以使用 Object 类来引用我们在 Java 中不知道其类型的任
- 希尔排序是插入排序的一种,又称"缩小增量排序”,是插入排序算法的一种更高效的改进版本。希尔排序原理1.选定一个增长量h,按照增长量
- 本文实例讲述了C#实现String类型和json之间的相互转换功能。分享给大家供大家参考,具体如下:////Donet2.0 需要添加引用/
- 1.Spring bean组件 ”默认为单例模式scope=“singleton, 运行JavaApplication容器启动时自动创建对象
- MyBatis-Plus是通过version机制实现乐观锁的。大致思路:取出记录,携带记录的当前version;更新记录的时候,比较记录当前
- 需求说明实际操作过程中,从D盘根目录下的ak.txt读取文件写入D盘根目录下的hello.txt文件内实现思路写两个方法,一个用于读取目标文
- 对于 * ,学过AOP的应该都不会陌生,因为代理是实现AOP功能的核心和关键技术。那么今天我们将开始 * 的学习:一、引出 * 生活中
- 一、消息队列概述消息队列中间件是分布式系统中重要的组件,主要解决应用解耦,异步消息,流量削锋等问题,实现高性能,高可用,可伸缩和最终一致性架