这是另一个O(n²)JAVA实现。不需要递归/记忆来生成实际的子序列。只是一个字符串数组，存储每个阶段的实际LIS和一个数组，存储每个元素的LIS的长度。非常简单。看看吧:

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Created by Shreyans on 4/16/2015
 */

class LNG_INC_SUB//Longest Increasing Subsequence
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter Numbers Separated by Spaces to find their LIS\n");
        String[] s1=br.readLine().split(" ");
        int n=s1.length;
        int[] a=new int[n];//Array actual of Numbers
        String []ls=new String[n];// Array of Strings to maintain LIS for every element
        for(int i=0;i<n;i++)
        {
            a[i]=Integer.parseInt(s1[i]);
        }
        int[]dp=new int[n];//Storing length of max subseq.
        int max=dp[0]=1;//Defaults
        String seq=ls[0]=s1[0];//Defaults
        for(int i=1;i<n;i++)
        {
            dp[i]=1;
            String x="";
            for(int j=i-1;j>=0;j--)
            {
                //First check if number at index j is less than num at i.
                // Second the length of that DP should be greater than dp[i]
                // -1 since dp of previous could also be one. So we compare the dp[i] as empty initially
                if(a[j]<a[i]&&dp[j]>dp[i]-1)
                {
                    dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j]
                    x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on
                }
            }
            x+=(" "+a[i]);
            ls[i]=x;
            if(dp[i]>max)
            {
                max=dp[i];
                seq=ls[i];
            }
        }
        System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq);
    }
}

实际代码:http://ideone.com/sBiOQx

说到DP solution，我发现很奇怪的是没有人提到LIS可以简化为LCS。你所需要做的就是对原始序列的副本进行排序，删除所有重复的副本，然后对它们进行LCS。在伪代码中是:

def LIS(S):
    T = sort(S)
    T = removeDuplicates(T)
    return LCS(S, T)

以及用Go语言编写的完整实现。如果你不需要重构解，你就不需要维护整个n^2 DP矩阵。

func lcs(arr1 []int) int {
    arr2 := make([]int, len(arr1))
    for i, v := range arr1 {
        arr2[i] = v
    }
    sort.Ints(arr1)
    arr3 := []int{}
    prev := arr1[0] - 1
    for _, v := range arr1 {
        if v != prev {
            prev = v
            arr3 = append(arr3, v)
        }
    }

    n1, n2 := len(arr1), len(arr3)

    M := make([][]int, n2 + 1)
    e := make([]int, (n1 + 1) * (n2 + 1))
    for i := range M {
        M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)]
    }

    for i := 1; i <= n2; i++ {
        for j := 1; j <= n1; j++ {
            if arr2[j - 1] == arr3[i - 1] {
                M[i][j] = M[i - 1][j - 1] + 1
            } else if M[i - 1][j] > M[i][j - 1] {
                M[i][j] = M[i - 1][j]
            } else {
                M[i][j] = M[i][j - 1]
            }
        }
    }

    return M[n2][n1]
}

这是我的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)

这可以用动态规划在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上分享了相同的代码

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(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;
}