最长递增子序列(Java)

import java.util.*;

class ChainHighestValue implements Comparable<ChainHighestValue>{
    int highestValue;
    int chainLength;
    ChainHighestValue(int highestValue,int chainLength) {
        this.highestValue = highestValue;
        this.chainLength = chainLength;
    }
    @Override
    public int compareTo(ChainHighestValue o) {
       return this.chainLength-o.chainLength;
    }

}


public class LongestIncreasingSubsequenceLinkedList {


    private static LinkedList<Integer> LongestSubsequent(int arr[], int size){
        ArrayList<LinkedList<Integer>> seqList=new ArrayList<>();
        ArrayList<ChainHighestValue> valuePairs=new ArrayList<>();
        for(int i=0;i<size;i++){
            int currValue=arr[i];
            if(valuePairs.size()==0){
                LinkedList<Integer> aList=new LinkedList<>();
                aList.add(arr[i]);
                seqList.add(aList);
                valuePairs.add(new ChainHighestValue(arr[i],1));

            }else{
                try{
                    ChainHighestValue heighestIndex=valuePairs.stream().filter(e->e.highestValue<currValue).max(ChainHighestValue::compareTo).get();
                    int index=valuePairs.indexOf(heighestIndex);
                    seqList.get(index).add(arr[i]);
                    heighestIndex.highestValue=arr[i];
                    heighestIndex.chainLength+=1;

                }catch (Exception e){
                    LinkedList<Integer> aList=new LinkedList<>();
                    aList.add(arr[i]);
                    seqList.add(aList);
                    valuePairs.add(new ChainHighestValue(arr[i],1));
                }
            }
        }
        ChainHighestValue heighestIndex=valuePairs.stream().max(ChainHighestValue::compareTo).get();
        int index=valuePairs.indexOf(heighestIndex);
        return seqList.get(index);
    }

    public static void main(String[] args){
        int arry[]={5,1,3,6,11,30,32,5,3,73,79};
        //int arryB[]={3,1,5,2,6,4,9};
        LinkedList<Integer> LIS=LongestSubsequent(arry, arry.length);
        System.out.println("Longest Incrementing Subsequence:");
        for(Integer a: LIS){
            System.out.print(a+" ");
        }

    }
}

这可以用动态规划在O(n²)中解决。

按顺序处理输入元素，并为每个元素维护一个元组列表。每个元组(A,B)，对于i将表示的元素，A =以i结尾的最长递增子序列的长度，B =以列表[i]结尾的最长递增子序列中列表[i]的前身的索引。

从元素1开始，元素1的元组列表为[(1,0)] 对于元素i，扫描列表0..i，找到元素list[k]，使得list[k] < list[i]，元素i的A值，Ai为Ak + 1, Bi为k。如果有多个这样的元素，将它们添加到元素i的元组列表中。

最后，找到所有最大值为A (LIS以element结尾的长度)的元素，并使用元组回溯以获得列表。

我已经在http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799上分享了相同的代码

c++中最简单的LIS解决方案，具有O(nlog(n))时间复杂度

#include <iostream>
#include "vector"
using namespace std;

// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
    if(beg<=end)
    {
        int mid = (beg+end)/2;
        if(a[mid] == value)
            return mid;
        else if(value < a[mid])
            return ceilBinarySearch(a,beg,mid-1,value);
        else
            return ceilBinarySearch(a,mid+1,end,value);

    return 0;
    }

    return beg;

}
int lis(vector<int> arr)
{
    vector<int> dp(arr.size(),0);
    int len = 0;
    for(int i = 0;i<arr.size();i++)
    {
        int j = ceilBinarySearch(dp,0,len-1,arr[i]);
        dp[j] = arr[i];
        if(j == len)
            len++;

    }
    return len;
}

int main()
{
    vector<int> arr  {2, 5,-1,0,6,1,2};
    cout<<lis(arr);
    return 0;
}

输出: 4

下面是O(n^2)算法的Scala实现:

object Solve {
  def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
    xs.foldLeft(List[(Int, List[T])]()) {
      (sofar, x) =>
        if (sofar.isEmpty) List((1, List(x)))
        else {
          val resIfEndsAtCurr = (sofar, xs).zipped map {
            (tp, y) =>
              val len = tp._1
              val seq = tp._2
              if (ord.lteq(y, x)) {
                (len + 1, x :: seq) // reversely recorded to avoid O(n)
              } else {
                (1, List(x))
              }
          }
          sofar :+ resIfEndsAtCurr.maxBy(_._1)
        }
    }.maxBy(_._1)._2.reverse
  }

  def main(args: Array[String]) = {
    println(longestIncrSubseq(List(
      0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)))
  }
}

下面是从动态规划的角度评估问题的三个步骤:

递归定义:maxLength(i) == 1 + maxLength(j) where 0 < j < i and array[i] > array[j] 递归参数边界:可能有0到i - 1个子序列作为参数传递 求值顺序:由于是递增子序列，所以要从0求值到n

如果我们以序列{0,8,2,3,7,9}为例，at index:

我们会得到子序列{0}作为基本情况 [1]有一个新的子序列{0,8} [2]试图评估两个新的序列{0,8,2}和{0,2}通过添加元素在索引2到现有的子序列-只有一个是有效的，所以添加第三个可能的序列{0,2}只到参数列表 .．.

下面是c++ 11的工作代码:

#include <iostream>
#include <vector>

int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
    if(index == 0) {
        sub.push_back(std::vector<int>{sequence[0]});
        return 1;
    }

    size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
    std::vector<std::vector<int>> tmpSubSeq;
    for(std::vector<int> &subSeq : sub) {
        if(subSeq[subSeq.size() - 1] < sequence[index]) {
            std::vector<int> newSeq(subSeq);
            newSeq.push_back(sequence[index]);
            longestSubSeq = std::max(longestSubSeq, newSeq.size());
            tmpSubSeq.push_back(newSeq);
        }
    }
    std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
              std::back_insert_iterator<std::vector<std::vector<int>>>(sub));

    return longestSubSeq;
}

int getLongestIncSub(const std::vector<int> &sequence) {
    std::vector<std::vector<int>> sub;
    return getLongestIncSub(sequence, sequence.size() - 1, sub);
}

int main()
{
    std::vector<int> seq{0, 8, 2, 3, 7, 9};
    std::cout << getLongestIncSub(seq);
    return 0;
}

求最长递增子序列(LIS)的O(NLog(N))递归DP方法

解释

该算法涉及创建节点格式为(a,b)的树。

A表示到目前为止我们考虑添加到有效子序列的下一个元素。

B表示剩余子数组的起始索引，如果a被添加到目前为止我们所拥有的子数组的末尾，则下一个决策将从该子数组开始。

算法

We start with an invalid root (INT_MIN,0), pointing at index zero of the array since subsequence is empty at this point, i.e. b = 0. Base Case: return 1 if b >= array.length. Loop through all the elements in the array from the b index to the end of the array, i.e i = b ... array.length-1. i) If an element, array[i] is greater than the current a, it is qualified to be considered as one of the elements to be appended to the subsequence we have so far. ii) Recurse into the node (array[i],b+1), where a is the element we encountered in 2(i) which is qualified to be appended to the subsequence we have so far. And b+1 is the next index of the array to be considered. iii) Return the max length obtained by looping through i = b ... array.length. In a case where a is bigger than any other element from i = b to array.length, return 1. Compute the level of the tree built as level. Finally, level - 1 is the desired LIS. That is the number of edges in the longest path of the tree.

注意:算法的记忆部分被省略了，因为它是从树中清除的。

随便举个例子 标记为x的节点从DB内存值中获取。

Java实现

public int lengthOfLIS(int[] nums) {
            return LIS(nums,Integer.MIN_VALUE, 0,new HashMap<>()) -1;
    }
    public int LIS(int[] arr, int value, int nextIndex, Map<String,Integer> memo){
        if(memo.containsKey(value+","+nextIndex))return memo.get(value+","+nextIndex);
        if(nextIndex >= arr.length)return 1;

        int max = Integer.MIN_VALUE;
        for(int i=nextIndex; i<arr.length; i++){
            if(arr[i] > value){
                max = Math.max(max,LIS(arr,arr[i],i+1,memo));
            }
        }
        if(max == Integer.MIN_VALUE)return 1;
        max++;
        memo.put(value+","+nextIndex,max);
        return max;
    }