Java实现求数组最长子序列算法示例
作者:antchow- 时间:2023-09-28 12:35:14
本文实例讲述了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
标签:Java,数组,最长子序列,算法
0
投稿
猜你喜欢
SpringBoot应用线上重启脚本的命令详解
2022-02-05 18:21:52
SpringBoot通过源码探究静态资源的映射规则实现
2022-03-26 19:05:53
Android Studio下载与安装简易教程
2022-05-28 10:25:30
Java设计模式中的命令模式
2023-11-20 04:26:46
Android实现扫一扫识别数字功能
2021-09-27 09:30:57
Java Spring的使用注解开发详解
2023-04-27 03:00:40
Java微信跳一跳操作指南
2022-07-06 11:14:36
Android编程实现google消息通知功能示例
2023-02-02 20:00:27
解决异常FileNotFoundException:class path resource找不到资源文件的问题
2021-12-26 18:24:14
Android应用开发中使用Fragment的入门学习教程
2023-05-17 04:30:59
android实现点击按钮控制图片切换
2022-10-16 02:38:55
C#词法分析器之词法分析的使用详解
2022-01-26 04:22:13
MyBatis控制台显示SQL语句的方法实现
2021-10-18 04:10:00
Spring Boot插件spring tool suite安装及使用详解
2021-12-15 03:29:23
SpringCloud服务注册和发现组件Eureka
2023-10-26 06:07:51
VMware虚拟机下hadoop1.x的安装方法
2023-07-27 08:01:40
Android Studio一直处于Building的两种解决方法
2022-06-13 23:05:22
Android设计模式之Builder模式解析
2022-02-11 20:07:46
springboot+mybatis+枚举处理器的实现
2023-11-06 00:48:04
Android-SPI学习笔记
2022-05-15 17:35:33