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算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
相关推荐
-
java数据结构与算法之双向循环队列的数组实现方法
本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p
-
Java实现求子数组和的最大值算法示例
本文实例讲述了Java实现求子数组和的最大值算法.分享给大家供大家参考,具体如下: 一般C和C++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感. 题目: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值. 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18. 实现代码: package arrDe
-
Java数组常用排序算法实例小结
本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo
-
Java对数组实现选择排序算法的实例详解
一. 算法描述 选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟
-
Java算法之最长公共子序列问题(LCS)实例分析
本文实例讲述了Java算法之最长公共子序列问题(LCS).分享给大家供大家参考,具体如下: 问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X= { x1, x2,-, xm},则另一序列Z= {z1, z2,-, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,-, ik},使得对于所有j=1,2,-,k有 Xij=Zj.例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,
-
详解Java数据结构和算法（有序数组和二分查找）
一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默
-
简单讲解奇偶排序算法及在Java数组中的实现
奇偶排序是一个比较有个性的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序 举例吧, 待排数组 [6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较 [2 1 6 4 5 9] 交
-
Java中打乱一个数组的2种公平算法分享
公平算法,打乱数组 这是前几天面试的时候遇见的一道题目,看到这个题首先想到了洗牌程序: 方法一:洗牌程序原理 在java.util包中的Collections类中的 shuffle方法,现在手工实现以下代码如下: package test.ms; import java.util.Random; public class Redistribute2 { public static void main(String[] args) { //define the array int[] s = {1
-
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的
-
Java实现合并两个有序序列算法示例
本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C
-
java实现的AES秘钥生成算法示例
本文实例讲述了java实现的AES秘钥生成算法.分享给大家供大家参考,具体如下: import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import javax.crypto.KeyGenerator; import javax.crypto.SecretKey; public class Test { public static void main(String[] args) { g
-
Java基于分治法实现的快速排序算法示例
本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static
-
Java实现的计算最大下标距离算法示例
本文实例讲述了Java实现的计算最大下标距离算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整形数组,找出最大下标距离j−i, 当且A[i] < A[j] 和 i < j 解法 复杂度:三次扫描,每次的复杂度O(N) 算法:{5,3,4,0,1,4,1} 找出从第一个元素开始的下降序列{5,3,0} i=3,j=6, j从尾部扫描 初始化,i=3, j=6, A[i]=0 实现代码 public static int maxindexdistance(int A[]) { boole
-
Java实现的猴子吃桃问题算法示例
本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) = f(3) -(f(3)/
-
Python编程实现数学运算求一元二次方程的实根算法示例
本文实例讲述了Python编程实现数学运算求一元二次方程的实根算法.分享给大家供大家参考,具体如下: 问题: 请定义一个函数quadratic(a, b, c),接收3个参数,返回一元二次方程:ax² + bx + c = 0的两个解. 实现代码: #!/usr/bin/env python # -*- coding: utf-8 -*- import math def quadratic(a,b,c): if a == 0: raise TypeError('a不能为0') if not is
-
C++二维数组中的查找算法示例
本文实例讲述了C++二维数组中的查找算法.分享给大家供大家参考,具体如下: 一.问题: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 二.实现代码: #include <iostream> #include <vector> using namespace std; bool Find(int target, vector<vector<int>
-
基于Java实现的一层简单人工神经网络算法示例
本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect
-
JS使用队列对数组排列，基数排序算法示例
本文实例讲述了JS使用队列对数组排列,基数排序算法.分享给大家供大家参考,具体如下: /* * 使用队列对数组排列,基数排序 *对于0~99的数字,基数排序将数组集扫描两次. * 第一次按个位上的数字进行排序, * 第二次按十位上的数字进行排序 * */ function Queue(){ this.dataStore = [];//存放队列的数组,初始化为空 this.enqueue = enqueue;//向队列尾部添加一个元素 this.dequeue = dequeue;//删除队首的元