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

O(n²)java实现:

void LIS(int arr[]){
        int maxCount[]=new int[arr.length];
        int link[]=new int[arr.length];
        int maxI=0;
        link[0]=0;
        maxCount[0]=0;

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if(arr[j]<arr[i] && ((maxCount[j]+1)>maxCount[i])){
                    maxCount[i]=maxCount[j]+1;
                    link[i]=j;
                    if(maxCount[i]>maxCount[maxI]){
                        maxI=i;
                    }
                }
            }
        }


        for (int i = 0; i < link.length; i++) {
            System.out.println(arr[i]+"   "+link[i]);
        }
        print(arr,maxI,link);

    }

    void print(int arr[],int index,int link[]){
        if(link[index]==index){
            System.out.println(arr[index]+" ");
            return;
        }else{
            print(arr, link[index], link);
            System.out.println(arr[index]+" ");
        }
    }

这可以用动态规划在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的最长递增子序列长度。

这里是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(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;
}

下面的c++实现还包括一些使用名为prev的数组构建实际最长递增子序列的代码。

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();

    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

没有堆栈的实现只是反转向量

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}