这是我使用二分查找的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)

我已经使用动态规划和记忆化在Java中实现了LIS。除了代码之外，我还进行了复杂度计算，即为什么它是O(n Log(base2) n)。因为我认为理论或逻辑解释虽好，但实际演示总是更容易理解。

package com.company.dynamicProgramming;

import java.util.HashMap;
import java.util.Map;

public class LongestIncreasingSequence {

    static int complexity = 0;

    public static void main(String ...args){


        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int n = arr.length;

        Map<Integer, Integer> memo = new HashMap<>();

        lis(arr, n, memo);

        //Display Code Begins
        int x = 0;
        System.out.format("Longest Increasing Sub-Sequence with size %S is -> ",memo.get(n));
        for(Map.Entry e : memo.entrySet()){

            if((Integer)e.getValue() > x){
                System.out.print(arr[(Integer)e.getKey()-1] + " ");
                x++;
            }
        }
        System.out.format("%nAnd Time Complexity for Array size %S is just %S ", arr.length, complexity );
        System.out.format( "%nWhich is equivalent to O(n Log n) i.e. %SLog(base2)%S is %S",arr.length,arr.length, arr.length * Math.ceil(Math.log(arr.length)/Math.log(2)));
        //Display Code Ends

    }



    static int lis(int[] arr, int n, Map<Integer, Integer> memo){

        if(n==1){
            memo.put(1, 1);
            return 1;
        }

        int lisAti;
        int lisAtn = 1;

        for(int i = 1; i < n; i++){
            complexity++;

            if(memo.get(i)!=null){
                lisAti = memo.get(i);
            }else {
                lisAti = lis(arr, i, memo);
            }

            if(arr[i-1] < arr[n-1] && lisAti +1 > lisAtn){
                lisAtn = lisAti +1;
            }
        }

        memo.put(n, lisAtn);
        return lisAtn;

    }
}

当我运行上述代码时 -

Longest Increasing Sub-Sequence with size 6 is -> 10 22 33 50 60 80 
And Time Complexity for Array size 9 is just 36 
Which is equivalent to O(n Log n) i.e. 9Log(base2)9 is 36.0
Process finished with exit code 0

这个问题可以使用动态规划在O(n^2)的时间复杂度内解决。相应的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)的时间复杂度内解决此问题。

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

从元素1开始，元素1的元组列表将为[(1,0)]。 对于元素i，扫描列表0..i并找到元素list[k]（其中k

最后，找到所有以A（以该元素结尾的LIS的长度）的最大值的元素，并使用元组回溯以获取列表。

我已经在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) 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(NLog(N))递归DP方法寻找最长上升子序列（LIS）

---

解释

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

a表示我们正在考虑附加到迄今为止有效子序列的下一个元素。

b表示剩余子数组的起始索引，如果将a附加到我们迄今为止拥有的子数组的末尾，则下一个决策将从中进行。

算法

1. 我们从一个无效的根节点 (INT_MIN,0) 开始，指向数组的索引零，因为此时子序列为空，即 b = 0。

2. 基本情况：如果 b >= array.length，则返回 1。

3. 循环遍历数组中从索引 b 到数组末尾的所有元素，即 i = b ... array.length-1。 i) 如果一个元素 array[i] 大于当前的 a，它就有资格被考虑作为迄今为止要附加到子序列中的元素之一。 ii) 递归进入节点 (array[i],b+1)，其中 a 是我们在 2(i) 中遇到的元素，它有资格被附加到我们迄今为止的子序列中。而 b+1 是要考虑的下一个数组索引。 iii) 返回通过循环遍历 i = b ... array.length 获得的最大长度。在 a 大于从 i = b to array.length 的任何其他元素的情况下，返回 1。

4. 计算建立的树的层数为 level。最后，level - 1 是所需的 LIS。即树的最长路径中的 边数。

NB：由于从树中可以清晰地看出算法的记忆部分，因此省略了它。

随机示例 标记为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(NLog(N))查找最长递增子序列的方法
让我们维护一个数组，其中第i个元素是以a[i]结尾的长度为i的子序列可能的最小值。

故意避免进一步的细节，因为排名第一的答案已经解释了它，但这种技术最终会导致使用集合数据结构（至少在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;
}

最长上升子序列（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+" ");
        }

    }
}

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^2)的时间），但这种方式仍然提供了动态规划的方法，这也是不错的。