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

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

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

最长递增子序列(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+" ");
        }

    }
}

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

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