我已经在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²)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(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

好的，我先描述最简单的解也就是O(N²)N是集合的大小。还有一个O(N log N)解，我也会讲到。在高效算法一节中可以找到。

我假设数组的下标从0到N - 1。因此，让我们定义DP[i]为LIS(最长递增子序列)的长度，它结束于索引为i的元素。为了计算DP[i]，我们查看所有索引j < i，并检查DP[j] + 1 > DP[i]和array[j] < array[i](我们希望它是递增的)。如果这是真的，我们可以更新DP[i]的当前最优值。要找到数组的全局最优值，您可以从DP[0…]N - 1]。

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}

我使用数组prev是为了以后能够找到实际的序列，而不仅仅是它的长度。只需在循环中使用prev[bestEnd]从bestEnd递归返回。-1值是停止的标志。

好了，现在来看更有效的O(nlog N)解:

设S[pos]定义为长度为pos的递增序列结束的最小整数。现在遍历输入集的每个整数X，并执行以下操作:

如果X >是S中的最后一个元素，那么将X附加到S的末尾，这本质上意味着我们已经找到了一个新的最大的LIS。 否则，找到S中最小的元素，即>= X，并将其改为X。 因为S在任何时候都是排序的，所以可以使用log(N)的二分搜索来找到元素。

总运行时间- N个整数，并对每个整数进行二进制搜索- N * log(N) = O(N log N)

现在我们来做一个真实的例子:

整数的集合: 2 6 3 4 1 2 9 5 8

步骤:

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS

所以LIS的长度是5 (S的大小)。

为了重建实际的LIS，我们将再次使用父数组。 设parent[i]是LIS中索引为i的元素的前身，该元素以索引为i的元素结束。

为了使事情更简单，我们可以在数组S中保留不是实际的整数，而是它们在集合中的下标(位置)。我们不保留{1,2,4,5,8}，而是保留{4,5,3,7,8}。

即输入[4]= 1，输入[5]= 2，输入[3]= 4，输入[7]= 5，输入[8]= 8。

如果我们正确地更新父数组，实际的LIS是:

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

现在重要的是，我们如何更新父数组?有两种选择:

如果X >是S中的最后一个元素，那么parent[indexX] = indexLastElement。这意味着最新元素的父元素是最后一个元素。我们只是在S的末尾加上X。 否则，找到S中最小元素的索引>= than X，并将其更改为X。这里parent[indexX] = S[index - 1]。

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

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