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

这可以用动态规划在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(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;
}

下面是从动态规划的角度评估问题的三个步骤:

递归定义: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(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

用Java签出包含数组元素的最长递增子序列的代码

http://ideone.com/Nd2eba

/**
 **    Java Program to implement Longest Increasing Subsequence Algorithm
 **/

import java.util.Scanner;

/** Class  LongestIncreasingSubsequence **/
 class  LongestIncreasingSubsequence
{
    /** function lis **/
    public int[] lis(int[] X)
    {        
        int n = X.length - 1;
        int[] M = new int[n + 1];  
        int[] P = new int[n + 1]; 
        int L = 0;

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

            /** Linear search applied here. Binary Search can be applied too.
                binary search for the largest positive j <= L such that 
                X[M[j]] < X[i] (or set j = 0 if no such value exists) **/

            for (int pos = L ; pos >= 1; pos--)
            {
                if (X[M[pos]] < X[i])
                {
                    j = pos;
                    break;
                }
            }            
            P[i] = M[j];
            if (j == L || X[i] < X[M[j + 1]])
            {
                M[j + 1] = i;
                L = Math.max(L,j + 1);
            }
        }

        /** backtrack **/

        int[] result = new int[L];
        int pos = M[L];
        for (int i = L - 1; i >= 0; i--)
        {
            result[i] = X[pos];
            pos = P[pos];
        }
        return result;             
    }

    /** Main Function **/
    public static void main(String[] args) 
    {    
        Scanner scan = new Scanner(System.in);
        System.out.println("Longest Increasing Subsequence Algorithm Test\n");

        System.out.println("Enter number of elements");
        int n = scan.nextInt();
        int[] arr = new int[n + 1];
        System.out.println("\nEnter "+ n +" elements");
        for (int i = 1; i <= n; i++)
            arr[i] = scan.nextInt();

        LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence(); 
        int[] result = obj.lis(arr);       

        /** print result **/ 

        System.out.print("\nLongest Increasing Subsequence : ");
        for (int i = 0; i < result.length; i++)
            System.out.print(result[i] +" ");
        System.out.println();
    }
}