By Tony


2010-04-13 17:26:50 8 Comments

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.

16 comments

@Ashish kumar 2019-07-17 18:31:53

Simplest LIS solution in C++ with O(nlog(n)) time complexity

#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;
}

OUTPUT:
4

@Abhinav Vajpeyi 2019-06-27 13:03:15

Here is my Leetcode solution using Binary Search:->

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)

@ravi tanwar 2018-07-06 15:16:50

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)

even though there is a way by which you can solve this in O(nlogn) time(this solves in O(n^2) time) but still this way gives the dynamic programming approach which is also good .

@Mostafizar 2017-02-17 20:27:54

O(n^2) java implementation:

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]+" ");
        }
    }

@Salvador Dali 2016-04-25 09:33:45

Speaking about DP solution, I found it surprising that no one mentioned the fact that LIS can be reduced to LCS. All you need to do is sort the copy of the original sequence, remove all the duplicates and do LCS of them. In pseudocode it is:

def LIS(S):
    T = sort(S)
    T = removeDuplicates(T)
    return LCS(S, T)

And the full implementation written in Go. You do not need to maintain the whole n^2 DP matrix if you do not need to reconstruct the solution.

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

@max 2017-06-28 18:06:33

That would be O(N^2) solution, right?

@Salvador Dali 2017-06-28 18:16:23

@max yes, it is kind of written in the answer with LCS, n^2 matrix

@Petar Minchev 2010-04-13 17:39:57

OK, I will describe first the simplest solution which is O(N^2), where N is the size of the collection. There also exists a O(N log N) solution, which I will describe also. Look here for it at the section Efficient algorithms.

I will assume the indices of the array are from 0 to N - 1. So let's define DP[i] to be the length of the LIS (Longest increasing subsequence) which is ending at element with index i. To compute DP[i] we look at all indices j < i and check both if DP[j] + 1 > DP[i] and array[j] < array[i] (we want it to be increasing). If this is true we can update the current optimum for DP[i]. To find the global optimum for the array you can take the maximum value from 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];
   }
}

I use the array prev to be able later to find the actual sequence not only its length. Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.


OK, now to the more efficient O(N log N) solution:

Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos. Now iterate through every integer X of the input set and do the following:

  1. If X > last element in S, then append X to the end of S. This essentialy means we have found a new largest LIS.

  2. Otherwise find the smallest element in S, which is >= than X, and change it to X. Because S is sorted at any time, the element can be found using binary search in log(N).

Total runtime - N integers and a binary search for each of them - N * log(N) = O(N log N)

Now let's do a real example:

Collection of integers: 2 6 3 4 1 2 9 5 8

Steps:

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

So the length of the LIS is 5 (the size of S).

To reconstruct the actual LIS we will again use a parent array. Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i.

To make things simpler, we can keep in the array S, not the actual integers, but their indices(positions) in the set. We do not keep {1, 2, 4, 5, 8}, but keep {4, 5, 3, 7, 8}.

That is input[4] = 1, input[5] = 2, input[3] = 4, input[7] = 5, input[8] = 8.

If we update properly the parent array, the actual LIS is:

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

Now to the important thing - how do we update the parent array? There are two options:

  1. If X > last element in S, then parent[indexX] = indexLastElement. This means the parent of the newest element is the last element. We just prepend X to the end of S.

  2. Otherwise find the index of the smallest element in S, which is >= than X, and change it to X. Here parent[indexX] = S[index - 1].

@SexyBeast 2012-11-02 07:52:47

The condition should be if (DP[j] + 1 >= DP[i] && array[j] < array[i]) instead of if (DP[j] + 1 > DP[i] && array[j] < array[i]), don't you think so?

@Petar Minchev 2012-11-02 09:10:49

It doesn't matter. If DP[j] + 1 == DP[i] then DP[i] won't become better with DP[i] = DP[j] + 1. We are trying to optimize DP[i].

@SexyBeast 2012-11-21 10:52:01

Can you explain the O(N log N) solution given at the link you mentioned? I cannot understand it..

@SexyBeast 2012-11-22 05:28:22

But here the answer should be [1,2,5,8], 4 comes before 1 in the array, how can the LIS be [1,2,4,5,8]?

@Petar Minchev 2012-11-22 08:26:22

@Cupidvogel - The answer is [2,3,4,5,8]. Read carefully - the S array DOES NOT represent an actual sequence. Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.

@SexyBeast 2012-11-22 08:43:54

So now the length of S is 5, so I know that the length of the LIS is 5. But how do I construct the actual LIS from it, like you did in your original solution?

@Petar Minchev 2012-11-22 08:49:16

@Petar Minchev 2012-11-22 09:13:40

I have updated my post. If you have any questions go to chat, by clicking continue this discussion in chat.

@Trying 2013-08-04 05:27:46

@PetarMinchev Nice explanation +1. Just have one doubt, can't i make this DP[j] + 1 > DP[i] to DP[j] >= DP[i]? Thanks.

@Petar Minchev 2013-08-04 08:04:02

Thank you! Yes, you can make it this way.

@hivert 2013-10-09 17:10:59

By the way, this algorithm is due to Craige Schensted.

@Snicolas 2014-01-14 05:16:39

It seems to that the first algorithm finds the longest increasing subsequence, and the second one finds the longest increasing subset.

@Petar Minchev 2014-01-14 07:23:14

Both algorithms find the longest increasing subsequence. What made you think the second algorithm is different?

@Snicolas 2014-01-14 14:27:07

Position of array elements are not taken into account for "sequencing". @PetarMinchev

@Petar Minchev 2014-01-14 15:43:38

Positions are taken into account. Please read the algorithm description at en.wikipedia.org/wiki/Longest_increasing_subsequence, in the section "Efficient algorithms".

@Petar Minchev 2014-01-19 19:39:10

@Kraken - Yes, using the prev array you will find only one subsequence. To find all subsequences you don't need the prev array. When restoring and you are at index cur, then you have to examine all previous indices i < cur, such that DP[i] = DP[cur] - 1 and array[i] < array[cur]. You can use recursion to print all.

@Kraken 2014-01-20 06:30:03

@PetarMinchev That will be using the first approach right? What about the second one? How do I do the entire process in nlogn?

@Petar Minchev 2014-01-20 11:48:05

@Kraken - Well you can also do the same for the second approach. To restore all sequences, you don't need the parent array. Just create another array DP, which will hold the length of LIS for each position in the array. When length of S is extended with one more element, then DP[i] = length(S). This was case 1. For case 2 - DP[i] = positionOfSmallestElementFoundWithBinarySearch. After having DP, then you can do the same as in my previous comment.

@Petar Minchev 2014-01-20 11:57:16

But doing effectively the process described in my previous comment is another story - then you have to examine all previous indices i < cur, such that DP[i] = DP[cur] - 1 and array[i] < array[cur].

@Boyang 2014-04-16 12:46:12

I don't often see such clear explanations. Not only it's very easy to understand, because the doubts are cleared within the explanation, but also it addresses any implementation problem that might arise. Awesome.

@candide 2014-05-06 10:08:23

+1 the step-by-step example. But : 1. (major) At first reading, I considered that every step in your example produces an increasing subsequence, the last step giving the requested subsequence. Indeed your comments give to understand that way (eg "New largest LIS"). Of course, this is not the case but it is easy to be confused : each step gives an increasing sequence of elements of the initial array T but NOT a SUBsequence of T; 2. (minor) a set data-structure has no natural order end no right side. However, you define the sequence to be built as a "set", eg "Initialize S to the empty set"

@Naman 2014-05-19 11:22:28

@PetarMinchev Hi Petar, I am solving a problem of finding ALL LIS. I used second method of O(nlogn) complexity. But if I print all solution using recursion on DP structure, won't it become slower? Is there any optimized way to print all LIS?

@Ben 2014-07-05 10:32:40

@PetarMinchev I've having some trouble understanding the parents array. Can you list how how the parent array is updated on each iteration?

@seeker 2014-08-01 20:56:04

How does your example work? Your second algorithm with the input {2 6 3 4 1 2 9 5 8} has a LIS of {2 3 4 5 8 } and NOT {1, 2, 4, 5, 8} . Can you explain whats happening there?

@Petar Minchev 2014-08-02 07:43:36

S is not containing the LIS. Read again "Let S[pos] be defined as the smallest integer that could possibly end an increasing sequence of length pos". To reconstruct the LIS you need the parent array.

@eb80 2014-08-02 20:16:21

geeksforgeeks.org/… is probably the best explanation of this i've seen

@Ali 2014-08-26 10:16:14

@PetarMinchev Amazing explanation. Much better than geeksforgeeks.org and Wikipedia itself. Thank you so much for explaining it this brief and clearly.

@bicepjai 2014-09-23 07:12:50

i could not understand 1) why do we have DP[j] + 1 > DP[i] this condition ? 2) how do we know that the array[j] < array[i] is going to verify that there are no numbers greater than array[j] before j ?

@Petar Minchev 2014-09-23 08:12:09

1) The condition is to make sure a smaller sequence doesn't overwrite a sequence of greater length. If DP[i] = 4, and DP[j] + 1 = 2, we don't want DP[i] to become 2 and to be overwritten with a smaller length.

@Petar Minchev 2014-09-23 08:16:56

2) You seem to be confused here. There can be numbers greater than array[j] before j and that is ok. The important thing is that we know that DP[j] is containing the length of a sequence of only strictly increasing numbers.

@harryg 2014-11-28 11:58:27

@Peter thanks for your explanation. I'm still struggling on how to construct the LIS array having constructed S. Updating the parent array doesn't seem to make sense. Do you do this in the same loop that you are finding S in?

@Petar Minchev 2014-11-29 09:42:53

Yes, immediately after changing something in S, you change the parent too. S is containing indices. S[pos] = the index of the smallest integer possible, which is the last number of a LIS of length pos. There are only two cases when updating S and for each case you update parent accordingly. The two cases are described at the end - prepending to end of S, or updating S somewhere in the inside of it.

@MortalMan 2016-03-09 01:04:37

@PetarMinchev Hi, can you please explain how to find the actual LIS using the O(N log N) algorithm?

@MortalMan 2016-03-09 01:50:54

also, how can S[lastElementOfS] exist, if S[8] doesn't exist?

@MortalMan 2016-03-09 02:22:39

You said this, about updating the parent array - We just prepend X to the end of S. Isn't that changing S, not the parent array?

@Greener 2016-03-12 21:41:05

I'm having a very hard time understanding why all definitions for "DP[i]" are "the length of the LIS(Longest increasing subsequence) which is ending at element with index i". Why do we define it as such? Couldn't we define DP[i] to be the length of the longest increasing sequence that's present in the array up to index i?

@arviman 2016-07-12 12:33:47

@Greener: because if you define DP[i] as length of LIS, then that doesn't help you build a substructure you can use to derive the higher answer order. Then, with the next value at index i+1, how do you know if it increases the LIS at any point in DP[0..i]. it just becomes like a greedy polynomial time solution.

@arviman 2016-07-12 12:35:10

I'm having a somewhat hard time parsing this: "Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i." - is it Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i or Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i.

@Adi agarwal 2016-12-04 18:08:56

@Somil Bhandari 2015-11-16 17:41:52

This can be solved in O(n^2) using dynamic programming.

Process the input elements in order and maintain a list of tuples for each element. Each tuple (A,B), for the element i will denotes, A = length of longest increasing sub-sequence ending at i and B = index of predecessor of list[i] in the longest increasing sub-sequence ending at list[i].

Start from element 1, the list of tuple for element 1 will be [(1,0)] for element i, scan the list 0..i and find element list[k] such that list[k] < list[i], the value of A for element i, Ai will be Ak + 1 and Bi will be k. If there are multiple such elements, add them to the list of tuples for element i.

In the end, find all the elements with max value of A (length of LIS ending at element) and backtrack using the tuples to get the list.

I have shared the code for same at http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799

@NathanOliver- Reinstate Monica 2015-11-16 18:19:01

You should include the code in your answer as links may break.

@bjackfly 2013-10-28 16:10:58

The following C++ implementation includes also some code that builds the actual longest increasing subsequence using an array called 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;
}

Implementation with no stack just reverse the vector

#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;
}

@jayant singh 2015-10-27 11:09:16

checkout the code in java for longest increasing subsequence with the array elements

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

@Sam King 2013-11-09 01:48:46

Petar Minchev's explanation helped clear things up for me, but it was hard for me to parse what everything was, so I made a Python implementation with overly-descriptive variable names and lots of comments. I did a naive recursive solution, the O(n^2) solution, and the O(n log n) solution.

I hope it helps clear up the algorithms!

The Recursive Solution

def recursive_solution(remaining_sequence, bigger_than=None):
    """Finds the longest increasing subsequence of remaining_sequence that is      
    bigger than bigger_than and returns it.  This solution is O(2^n)."""

    # Base case: nothing is remaining.                                             
    if len(remaining_sequence) == 0:
        return remaining_sequence

    # Recursive case 1: exclude the current element and process the remaining.     
    best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)

    # Recursive case 2: include the current element if it's big enough.            
    first = remaining_sequence[0]

    if (first > bigger_than) or (bigger_than is None):

        sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)

        # Choose whichever of case 1 and case 2 were longer.                         
        if len(sequence_with) >= len(best_sequence):
            best_sequence = sequence_with

    return best_sequence                                                        

The O(n^2) Dynamic Programming Solution

def dynamic_programming_solution(sequence):
    """Finds the longest increasing subsequence in sequence using dynamic          
    programming.  This solution is O(n^2)."""

    longest_subsequence_ending_with = []
    backreference_for_subsequence_ending_with = []
    current_best_end = 0

    for curr_elem in range(len(sequence)):
        # It's always possible to have a subsequence of length 1.                    
        longest_subsequence_ending_with.append(1)

        # If a subsequence is length 1, it doesn't have a backreference.             
        backreference_for_subsequence_ending_with.append(None)

        for prev_elem in range(curr_elem):
            subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)

            # If the prev_elem is smaller than the current elem (so it's increasing)   
            # And if the longest subsequence from prev_elem would yield a better       
            # subsequence for curr_elem.                                               
            if ((sequence[prev_elem] < sequence[curr_elem]) and
                    (subsequence_length_through_prev >
                         longest_subsequence_ending_with[curr_elem])):

                # Set the candidate best subsequence at curr_elem to go through prev.    
                longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
                backreference_for_subsequence_ending_with[curr_elem] = prev_elem
                # If the new end is the best, update the best.    

        if (longest_subsequence_ending_with[curr_elem] >
                longest_subsequence_ending_with[current_best_end]):
            current_best_end = curr_elem
            # Output the overall best by following the backreferences.  

    best_subsequence = []
    current_backreference = current_best_end

    while current_backreference is not None:
        best_subsequence.append(sequence[current_backreference])
        current_backreference = (backreference_for_subsequence_ending_with[current_backreference])

    best_subsequence.reverse()

    return best_subsequence                                                   

The O(n log n) Dynamic Programming Solution

def find_smallest_elem_as_big_as(sequence, subsequence, elem):
    """Returns the index of the smallest element in subsequence as big as          
    sequence[elem].  sequence[elem] must not be larger than every element in       
    subsequence.  The elements in subsequence are indices in sequence.  Uses       
    binary search."""

    low = 0
    high = len(subsequence) - 1

    while high > low:
        mid = (high + low) / 2
        # If the current element is not as big as elem, throw out the low half of    
        # sequence.                                                                  
        if sequence[subsequence[mid]] < sequence[elem]:
            low = mid + 1
            # If the current element is as big as elem, throw out everything bigger, but 
        # keep the current element.                                                  
        else:
            high = mid

    return high


def optimized_dynamic_programming_solution(sequence):
    """Finds the longest increasing subsequence in sequence using dynamic          
    programming and binary search (per                                             
    http://en.wikipedia.org/wiki/Longest_increasing_subsequence).  This solution   
    is O(n log n)."""

    # Both of these lists hold the indices of elements in sequence and not the        
    # elements themselves.                                                         
    # This list will always be sorted.                                             
    smallest_end_to_subsequence_of_length = []

    # This array goes along with sequence (not                                     
    # smallest_end_to_subsequence_of_length).  Following the corresponding element 
    # in this array repeatedly will generate the desired subsequence.              
    parent = [None for _ in sequence]

    for elem in range(len(sequence)):
        # We're iterating through sequence in order, so if elem is bigger than the   
        # end of longest current subsequence, we have a new longest increasing          
        # subsequence.                                                               
        if (len(smallest_end_to_subsequence_of_length) == 0 or
                    sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
            # If we are adding the first element, it has no parent.  Otherwise, we        
            # need to update the parent to be the previous biggest element.            
            if len(smallest_end_to_subsequence_of_length) > 0:
                parent[elem] = smallest_end_to_subsequence_of_length[-1]
            smallest_end_to_subsequence_of_length.append(elem)
        else:
            # If we can't make a longer subsequence, we might be able to make a        
            # subsequence of equal size to one of our earlier subsequences with a         
            # smaller ending number (which makes it easier to find a later number that 
            # is increasing).                                                          
            # Thus, we look for the smallest element in                                
            # smallest_end_to_subsequence_of_length that is at least as big as elem       
            # and replace it with elem.                                                
            # This preserves correctness because if there is a subsequence of length n 
            # that ends with a number smaller than elem, we could add elem on to the   
            # end of that subsequence to get a subsequence of length n+1.              
            location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
            smallest_end_to_subsequence_of_length[location_to_replace] = elem
            # If we're replacing the first element, we don't need to update its parent 
            # because a subsequence of length 1 has no parent.  Otherwise, its parent  
            # is the subsequence one shorter, which we just added onto.                
            if location_to_replace != 0:
                parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])

    # Generate the longest increasing subsequence by backtracking through parent.  
    curr_parent = smallest_end_to_subsequence_of_length[-1]
    longest_increasing_subsequence = []

    while curr_parent is not None:
        longest_increasing_subsequence.append(sequence[curr_parent])
        curr_parent = parent[curr_parent]

    longest_increasing_subsequence.reverse()

    return longest_increasing_subsequence         

@Johan S 2014-01-27 08:52:20

Your optimized algorithm is incorrect. Please test the case when sequence is 5, 19, 5, 81, 50, 28, 29, 1, 83, 23. Your algorithm returns 5, 19, 81, 83 when it should return 5, 19, 28, 29, 83.

@Sam King 2014-02-24 07:01:02

Are you sure? When I run optimized_dynamic_programming_solution([5, 19, 5, 81, 50, 28, 29, 1, 83, 23]) on my computer, it returns [5, 19, 28, 29, 83].

@mostruash 2014-06-12 09:01:28

Although I appreciate the effort here, my eyes hurt when I stare at those pseudo-codes.

@Sam King 2014-06-12 15:39:39

mostruash -- I'm not sure what you mean. My answer doesn't have pseudo code; it has Python.

@Adilli Adil 2015-01-04 18:16:42

Well he most probably means your naming convention of variables and functions,which also made my eyes 'hurt'

@Sam King 2015-01-04 23:54:28

If you mean my naming convention, I'm mostly following the Google Python Style Guide. If you are advocating short variable names, I prefer descriptive variable names because they make code easier to understand and maintain.

@ihadanny 2015-04-05 16:37:31

cool. but don't you think using bisect instead of find_smallest_elem_as_big_as would clear it up?

@Sam King 2015-04-05 20:04:34

For an actual implementation, it would probably make sense to use bisect. For a demonstration of how an algorithm works and its performance characteristics, I was trying to keep things as primitive as possible.

@Will 2015-11-05 23:06:54

@SamKing where did you get your recursive solution from?

@Will 2015-11-05 23:29:53

@Alperen 2017-10-09 13:23:54

This is a very useful solution, but I need to note that I took TypeError: list indices must be integers or slices, not float error in dynamic solution code because of the line mid = (high + low) / 2. I guess, it should be mid = (high + low) // 2 or mid = int((high + low) / 2)

@Sam King 2017-10-09 17:29:23

All of the code is working python2 code. If you're running it in python3, you might have some issues.

@Shashank Agarwal 2015-03-08 22:55:54

This is a Java implementation in O(n^2). I just did not use Binary Search to find the smallest element in S, which is >= than X. I just used a for loop. Using Binary Search would make the complexity at 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));

}

@fatih tekin 2015-05-14 18:20:24

here is java O(nlogn) implementation

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

@bholagabbar 2015-04-16 15:56:21

Here's another O(n^2) JAVA implementation. No recursion/memoization to generate the actual subsequence. Just a string array that stores the actual LIS at every stage and an array to store the length of the LIS for each element. Pretty darn easy. Have a look:

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

Code in action: http://ideone.com/sBiOQx

@lcn 2014-12-14 05:21:55

Here is a Scala implementation of the O(n^2) algorithm:

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)))
  }
}

@Barun Sharma 2014-04-13 19:57:01

This can be solved in O(n^2) using Dynamic Programming. Python code for the same would be like:-

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)

For input:5 19 5 81 50 28 29 1 83 23

output would be:[1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

The list_index of output list is the list_index of input list. The value at a given list_index in output list denotes the Longest increasing subsequence length for that list_index.

@Iuri Covalisin 2013-11-13 00:54:34

Here are three steps of evaluating the problem from dynamic programming point of view:

  1. Recurrence definition: maxLength(i) == 1 + maxLength(j) where 0 < j < i and array[i] > array[j]
  2. Recurrence parameter boundary: there might be 0 to i - 1 sub-sequences passed as a paramter
  3. Evaluation order: as it is increasing sub-sequence, it has to be evaluated from 0 to n

If we take as an example sequence {0, 8, 2, 3, 7, 9}, at index:

  • [0] we'll get subsequence {0} as a base case
  • [1] we have 1 new subsequence {0, 8}
  • [2] trying to evaluate two new sequences {0, 8, 2} and {0, 2} by adding element at index 2 to existing sub-sequences - only one is valid, so adding third possible sequence {0, 2} only to parameters list ...

Here's the working C++11 code:

#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;
}

@Slothworks 2016-10-16 04:29:04

I think the recurrence definition should be maxLength(i) = 1 + max(maxLength(j)) for 0 < j < i and array[i] > array[j] rather than without the max().

Related Questions

Sponsored Content

10 Answered Questions

[SOLVED] What is dynamic programming?

44 Answered Questions

38 Answered Questions

[SOLVED] Find an integer not among four billion given ones

11 Answered Questions

[SOLVED] Dynamic programming: Find longest subsequence that is zig zag

2 Answered Questions

1 Answered Questions

[SOLVED] Longest Increasing Subsequence, Dynamic Programing

1 Answered Questions

0 Answered Questions

Number of longest increasing subsequences

  • 2014-02-23 14:15:49
  • user3328621
  • 238 View
  • 0 Score
  • 0 Answer
  • Tags:   java algorithm lis

1 Answered Questions

[SOLVED] Determine which items in an array are part of longest increasing subsequence(s)

  • 2014-05-20 14:06:48
  • Craig Gidney
  • 120 View
  • 1 Score
  • 1 Answer
  • Tags:   algorithm lis

Sponsored Content