最长递增子序列(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+" ");
        }

    }
}

这里是java O(nlogn)的实现

import java.util.Scanner;

public class LongestIncreasingSeq {


    private static int binarySearch(int table[],int a,int len){

        int end = len-1;
        int beg = 0;
        int mid = 0;
        int result = -1;
        while(beg <= end){
            mid = (end + beg) / 2;
            if(table[mid] < a){
                beg=mid+1;
                result = mid;
            }else if(table[mid] == a){
                return len-1;
            }else{
                end = mid-1;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {        
        
//        int[] t = {1, 2, 5,9,16};
//        System.out.println(binarySearch(t , 9, 5));
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();//4;
        
        int A[] = new int[size];
        int table[] = new int[A.length]; 
        int k = 0;
        while(k<size){
            A[k++] = in.nextInt();
            if(k<size-1)
                in.nextLine();
        }        
        table[0] = A[0];
        int len = 1; 
        for (int i = 1; i < A.length; i++) {
            if(table[0] > A[i]){
                table[0] = A[i];
            }else if(table[len-1]<A[i]){
                table[len++]=A[i];
            }else{
                table[binarySearch(table, A[i],len)+1] = A[i];
            }            
        }
        System.out.println(len);
    }    
}

//可以使用TreeSet

这可以用动态规划在O(n²)中解决。同样的Python代码是这样的:-

def LIS(numlist):
    LS = [1]
    for i in range(1, len(numlist)):
        LS.append(1)
        for j in range(0, i):
            if numlist[i] > numlist[j] and LS[i]<=LS[j]:
                LS[i] = 1 + LS[j]
    print LS
    return max(LS)

numlist = map(int, raw_input().split(' '))
print LIS(numlist)

输入:5 19 5 81 50 28 29 1 83 23

输出将是:[1,2,1,3,3,3,4,1,5,3] 5

输出列表的list_index是输入列表的list_index。输出列表中给定list_index的值表示该list_index的最长递增子序列长度。

下面是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;
}

求最长递增子序列的O(NLog(N))方法 让我们维护一个数组，其中第i个元素是一个大小为i的子序列可以结束的最小的数字。

我故意避免进一步的细节，因为投票最多的答案已经解释了它，但这种技术最终导致使用set数据结构的整洁实现(至少在c++中)。

下面是c++中的实现(假设需要严格增加最长子序列的大小)

#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;

int main()
{
  ll n;
  cin >> n;
  ll arr[n];
  set<ll> S;

  for(ll i=0; i<n; i++)
  {
    cin >> arr[i];
    auto it = S.lower_bound(arr[i]);
    if(it != S.end())
      S.erase(it);
    S.insert(arr[i]);
  }

  cout << S.size() << endl; // Size of the set is the required answer

  return 0;
}