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实现代码：
publicclassarrDemo{
publicstaticvoidmain(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};
intmax=0;
intmaxLen=arr.length;
//从后往前遍历数组，分别求出以arr[i]结尾的时候的最长子序列长度
for(inti=arr.length-1;i>0;i--){
int[]newArr=newint[i];
System.arraycopy(arr,0,newArr,0,i);
intcurrentLength=1+dp(newArr,arr[i]);
if(currentLength>max)
max=currentLength;
//最长子序列的长度最长为原始数组的长度，
//因为不需要我们求最长子序列的元素，所以直接结束循环，减少时间开销
if(max==maxLen)
break;
}
System.out.println(max);
}
publicstaticintdp(int[]arr,intend){
//递归结束条件
if(arr.length==1){
//小于end则包含在子序列中，子序列长度+1
if(arr[0]<=end)
return1;
else
return0;
}
//遍历数组，找到最靠近end的并且<=end的元素位置i
for(inti=arr.length-1;i>=0;i--){
if(arr[i]<=end){
//从i处截断数组，将arr[0]到arr[i-1]组成新数组继续递归求长度
int[]newArr=newint[i];
System.arraycopy(arr,0,newArr,0,i);
//分别计算包含arr[i]时的最长子序列和不包含arr[i]时的最长子序列，取最大值
intcontainLen=dp(newArr,arr[i])+1;
intnotContainLen=dp(newArr,end);
returncontainLen>notContainLen?containLen:notContainLen;
}
}
//如果没找到比end更小的，返回长度为0
return0;
}
}
运行结果：
6
我的方法由于中间开辟了多个新数组，可能占用的空间有点多，不过我觉得应该也不是很多--，具体我也没统计过。如果有不对的地方还请指正。
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。