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²)时间内解决)但这种方法仍然提供了动态规划方法，这也是很好的。

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

说到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]
}

这可以用动态规划在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实现。不需要递归/记忆来生成实际的子序列。只是一个字符串数组，存储每个阶段的实际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