这是一个O(n²)的Java实现。我只是没有使用二分搜索来找到S中最小的元素，它是>= than x，我只是使用了一个for循环。使用二分搜索将使复杂度为O(n logn)

public static void olis(int[] seq){

    int[] memo = new int[seq.length];

    memo[0] = seq[0];
    int pos = 0;

    for (int i=1; i<seq.length; i++){

        int x = seq[i];

            if (memo[pos] < x){ 
                pos++;
                memo[pos] = x;
            } else {

                for(int j=0; j<=pos; j++){
                    if (memo[j] >= x){
                        memo[j] = x;
                        break;
                    }
                }
            }
            //just to print every step
            System.out.println(Arrays.toString(memo));
    }

    //the final array with the LIS
    System.out.println(Arrays.toString(memo));
    System.out.println("The length of lis is " + (pos + 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)

这可以用动态规划在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的最长递增子序列长度。

下面的c++实现还包括一些使用名为prev的数组构建实际最长递增子序列的代码。

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();

    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

没有堆栈的实现只是反转向量

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}

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

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