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

def longestincrsub(arr1):
    n=len(arr1)
    l=[1]*n
    for i in range(0,n):
        for j in range(0,i)  :
            if arr1[j]<arr1[i] and l[i]<l[j] + 1:
                l[i] =l[j] + 1
    l.sort()
    return l[-1]
arr1=[10,22,9,33,21,50,41,60]
a=longestincrsub(arr1)
print(a)

尽管有一种方法可以在O(nlogn)时间内解决这个问题(它在O(n²)时间内解决)但这种方法仍然提供了动态规划方法，这也是很好的。

这是一个O(n²)的Java实现。我只是没有使用二分搜索来找到S中最小的元素，它是>= than x，我只是使用了一个for循环。使用二分搜索将使复杂度为O(n logn)

public static void olis(int[] seq){

    int[] memo = new int[seq.length];

    memo[0] = seq[0];
    int pos = 0;

    for (int i=1; i<seq.length; i++){

        int x = seq[i];

            if (memo[pos] < x){ 
                pos++;
                memo[pos] = x;
            } else {

                for(int j=0; j<=pos; j++){
                    if (memo[j] >= x){
                        memo[j] = x;
                        break;
                    }
                }
            }
            //just to print every step
            System.out.println(Arrays.toString(memo));
    }

    //the final array with the LIS
    System.out.println(Arrays.toString(memo));
    System.out.println("The length of lis is " + (pos + 1));

}

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

这是我的Leetcode解决方案使用二进制搜索:->

class Solution:
    def binary_search(self,s,x):
        low=0
        high=len(s)-1
        flag=1
        while low<=high:
              mid=(high+low)//2
              if s[mid]==x:
                 flag=0
                 break
              elif s[mid]<x:
                  low=mid+1
              else:
                 high=mid-1
        if flag:
           s[low]=x
        return s

    def lengthOfLIS(self, nums: List[int]) -> int:
         if not nums:
            return 0
         s=[]
         s.append(nums[0])
         for i in range(1,len(nums)):
             if s[-1]<nums[i]:
                s.append(nums[i])
             else:
                 s=self.binary_search(s,nums[i])
         return len(s)

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