使用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怎么计算数组中最长的子序列-创新互联
路径分享:http://pwwzsj.com/article/ddeidp.html