c++中最简单的LIS解决方案，具有O(nlog(n))时间复杂度

#include <iostream>
#include "vector"
using namespace std;

// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
    if(beg<=end)
    {
        int mid = (beg+end)/2;
        if(a[mid] == value)
            return mid;
        else if(value < a[mid])
            return ceilBinarySearch(a,beg,mid-1,value);
        else
            return ceilBinarySearch(a,mid+1,end,value);

    return 0;
    }

    return beg;

}
int lis(vector<int> arr)
{
    vector<int> dp(arr.size(),0);
    int len = 0;
    for(int i = 0;i<arr.size();i++)
    {
        int j = ceilBinarySearch(dp,0,len-1,arr[i]);
        dp[j] = arr[i];
        if(j == len)
            len++;

    }
    return len;
}

int main()
{
    vector<int> arr  {2, 5,-1,0,6,1,2};
    cout<<lis(arr);
    return 0;
}

输出: 4

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

递归定义: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²)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]。

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

最长递增子序列(Java)

import java.util.*;

class ChainHighestValue implements Comparable<ChainHighestValue>{
    int highestValue;
    int chainLength;
    ChainHighestValue(int highestValue,int chainLength) {
        this.highestValue = highestValue;
        this.chainLength = chainLength;
    }
    @Override
    public int compareTo(ChainHighestValue o) {
       return this.chainLength-o.chainLength;
    }

}


public class LongestIncreasingSubsequenceLinkedList {


    private static LinkedList<Integer> LongestSubsequent(int arr[], int size){
        ArrayList<LinkedList<Integer>> seqList=new ArrayList<>();
        ArrayList<ChainHighestValue> valuePairs=new ArrayList<>();
        for(int i=0;i<size;i++){
            int currValue=arr[i];
            if(valuePairs.size()==0){
                LinkedList<Integer> aList=new LinkedList<>();
                aList.add(arr[i]);
                seqList.add(aList);
                valuePairs.add(new ChainHighestValue(arr[i],1));

            }else{
                try{
                    ChainHighestValue heighestIndex=valuePairs.stream().filter(e->e.highestValue<currValue).max(ChainHighestValue::compareTo).get();
                    int index=valuePairs.indexOf(heighestIndex);
                    seqList.get(index).add(arr[i]);
                    heighestIndex.highestValue=arr[i];
                    heighestIndex.chainLength+=1;

                }catch (Exception e){
                    LinkedList<Integer> aList=new LinkedList<>();
                    aList.add(arr[i]);
                    seqList.add(aList);
                    valuePairs.add(new ChainHighestValue(arr[i],1));
                }
            }
        }
        ChainHighestValue heighestIndex=valuePairs.stream().max(ChainHighestValue::compareTo).get();
        int index=valuePairs.indexOf(heighestIndex);
        return seqList.get(index);
    }

    public static void main(String[] args){
        int arry[]={5,1,3,6,11,30,32,5,3,73,79};
        //int arryB[]={3,1,5,2,6,4,9};
        LinkedList<Integer> LIS=LongestSubsequent(arry, arry.length);
        System.out.println("Longest Incrementing Subsequence:");
        for(Integer a: LIS){
            System.out.print(a+" ");
        }

    }
}

这是一个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));

}