欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现求数组最长子序列算法示例

程序员文章站 2024-02-18 23:36:22
本文实例讲述了java实现求数组最长子序列算法。分享给大家供大家参考,具体如下: 问题:给定一个长度为n的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)...

本文实例讲述了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并发Timer源码分析

下一篇: