How to determine the longest increasing subsequence using dynamic programming

Question

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

User · Answer

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   gt  numlist j  and LS i  lt  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

User · Answer

The O NLog N   Recursive DP Approach To Finding the Longest Increasing Subsequence  LIS   Explanation This algorithm involves creating a tree with node format as  a b   a represents the next element we are considering appending to the valid subsequence so far  b represents the starting index of the remaining subarray that the next decision will be made from if a gets appended to the end of the subarray we have so far  Algorithm  We start with an invalid root  INT MIN 0   pointing at index zero of the array since subsequence is empty at this point  i e  b   0   Base Case  return 1 if b  gt   array length   Loop through all the elements in the array from the b index to the end of the array  i e i   b     array length-1  i  If an element  array i  is greater than the current a  it is qualified to be considered as one of the elements to be appended to the subsequence we have so far  ii   Recurse into the node  array i  b 1   where a is the element we encountered in 2 i  which is qualified to be appended to the subsequence we have so far  And b 1 is the next index of the array to be considered  iii  Return the max length obtained by looping through i   b     array length  In a case where a is bigger than any other element from i   b to array length  return 1   Compute the level of the tree built as level  Finally  level - 1 is the desired LIS  That is the number of edges in the longest path of the tree    NB  The memorization part of the algorithm is left out since it s clear from the tree  Random Example Nodes marked x are fetched from the DB memoized values   Java Implementation public int lengthOfLIS int   nums                return LIS nums Integer MIN VALUE  0 new HashMap lt  gt     -1            public int LIS int   arr  int value  int nextIndex  Map lt String Integer gt  memo           if memo containsKey value  quot   quot  nextIndex  return memo get value  quot   quot  nextIndex           if nextIndex  gt   arr length return 1           int max   Integer MIN VALUE          for int i nextIndex  i lt arr length  i                 if arr i   gt  value                   max   Math max max LIS arr arr i  i 1 memo                                    if max    Integer MIN VALUE return 1          max            memo put value  quot   quot  nextIndex max           return max

User · Answer

The following C   implementation includes also some code that builds the actual longest increasing subsequence using an array called prev   std  vector lt int gt  longest increasing subsequence  const std  vector lt int gt  amp  s        int best end   0      int sz   s size         if   sz          return std  vector lt int gt          std  vector lt int gt  prev sz -1       std  vector lt int gt  memo sz  0        int max length   std  numeric limits lt int gt   min         memo 0    1       for   auto i   1  i  lt  sz    i                for   auto j   0  j  lt  i    j                        if   s j   lt  s i   amp  amp  memo i   lt  memo j    1                                 memo i     memo j    1                  prev i     j                                   if   memo i   gt  max length                          best end   i              max length   memo i                           Code that builds the longest increasing subsequence using  prev      std  vector lt int gt  results      results reserve sz        std  stack lt int gt  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  lt iostream gt   include  lt vector gt   include  lt limits gt  std  vector lt int gt  LIS  const std  vector lt int gt   amp v       auto sz   v size      if  sz      return v    std  vector lt int gt  memo sz  0     std  vector lt int gt  prev sz  -1     memo 0    1    int best end   0    int max length   std  numeric limits lt int gt   min      for  auto i   1  i  lt  sz    i        for   auto j   0  j  lt  i     j          if  s j   lt  s i   amp  amp  memo i   lt  memo j    1            memo i    memo j    1          prev i    j                    if memo i   gt  max length          best end   i        max length   memo i                   create results   std  vector lt int gt  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

User · Answer

def longestincrsub arr1       n len arr1      l  1  n     for i in range 0 n           for j in range 0 i                 if arr1 j  lt arr1 i  and l i  lt 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

User · Answer

The O NLog N   Approach To Find Longest Increasing Sub sequence Let us maintain an array where the ith element is the smallest possible number with which a i sized sub sequence can end  On purpose I am avoiding further details as the top voted answer already explains it  but this technique eventually leads to a neat implementation using the set data structure  at least in c     Here is the implementation in c    assuming strictly increasing longest sub sequence size is required   include  lt bits stdc   h gt     gcc supported header to include  almost  everything using namespace std  typedef long long ll   int main       ll n    cin  gt  gt  n    ll arr n     set lt ll gt  S     for ll i 0  i lt n  i            cin  gt  gt  arr i       auto it   S lower bound arr i        if it    S end          S erase it       S insert arr i           cout  lt  lt  S size    lt  lt  endl     Size of the set is the required answer    return 0

User · Answer

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  lt   n2  i             for j    1  j  lt   n1  j                 if arr2 j - 1     arr3 i - 1                    M i  j    M i - 1  j - 1    1               else if M i - 1  j   gt  M i  j - 1                    M i  j    M i - 1  j                else                   M i  j    M i  j - 1                                     return M n2  n1

User · Answer

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 lt  high                mid  high low   2               if s mid   x                   flag 0                  break               elif s mid  lt x                    low mid 1               else                   high mid-1         if flag             s low  x         return s      def lengthOfLIS self  nums  List int   - gt  int           if not nums              return 0          s             s append nums 0            for i in range 1 len nums                 if s -1  lt nums i                   s append nums i                else                   s self binary search s nums i            return len s

User · Answer

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    gt          if  sofar isEmpty  List  1  List x            else             val resIfEndsAtCurr    sofar  xs  zipped map                tp  y    gt                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

User · Answer

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   lt  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

User · Answer

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  gt  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   gt   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   lt  sequence curr elem   and                      subsequence length through prev  gt                           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   gt                  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  gt  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    lt  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   gt  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   gt  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

User · Answer

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  lt  n   1  i                          int j   0                   Linear search applied here  Binary Search can be applied too                  binary search for the largest positive j  lt   L such that                  X M j    lt  X i   or set j   0 if no such value exists                   for  int pos   L   pos  gt   1  pos--                                if  X M pos    lt  X i                                         j   pos                      break                                                          P i    M j               if  j    L    X i   lt  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  gt   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  lt   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  lt  result length  i                System out print result i                 System out println

User · Answer

I have implemented LIS in java using Dynamic Programming and Memoization  Along with the code I have done complexity calculation i e  why it is O n Log base2  n   As I feel theoretical or logical explanations are good but practical demonstration is always better for understanding   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 lt Integer  Integer gt  memo   new HashMap lt  gt              lis arr  n  memo              Display Code Begins         int x   0          System out format  Longest Increasing Sub-Sequence with size  S is - gt    memo get n            for Map Entry e   memo entrySet                  if  Integer e getValue    gt  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 lt Integer  Integer gt  memo            if n  1               memo put 1  1               return 1                     int lisAti          int lisAtn   1           for int i   1  i  lt  n  i                 complexity                 if memo get i   null                   lisAti   memo get i                else                   lisAti   lis arr  i  memo                              if arr i-1   lt  arr n-1   amp  amp  lisAti  1  gt  lisAtn                   lisAtn   lisAti  1                                   memo put n  lisAtn           return lisAtn              While I ran the above code -   Longest Increasing Sub-Sequence with size 6 is - gt  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

User · Answer

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  lt   end               mid    end   beg    2              if table mid   lt  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 lt size               A k      in nextInt                if k lt size-1                  in nextLine                              table 0    A 0           int len   1           for  int i   1  i  lt  A length  i                  if table 0   gt  A i                    table 0    A i                else if table len-1  lt A i                    table len    A i                else                  table binarySearch table  A i  len  1    A i                                               System out println len                  TreeSet can be used

User · Answer

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 lt seq length  i              int x   seq i                if  memo pos   lt  x                    pos                    memo pos    x                else                    for int j 0  j lt  pos  j                         if  memo j   gt   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

User · Answer

Here are three steps of evaluating the problem from dynamic programming point of view    Recurrence definition  maxLength i     1   maxLength j  where 0  lt  j  lt  i and array i    array j  Recurrence parameter boundary  there might be 0 to i - 1 sub-sequences passed as a paramter 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  lt iostream gt   include  lt vector gt   int getLongestIncSub const std  vector lt int gt   amp sequence  size t index  std  vector lt std  vector lt int gt  gt   amp sub        if index    0            sub push back std  vector lt int gt  sequence 0             return 1             size t longestSubSeq   getLongestIncSub sequence  index - 1  sub       std  vector lt std  vector lt int gt  gt  tmpSubSeq      for std  vector lt int gt   amp subSeq   sub            if subSeq subSeq size   - 1   lt  sequence index                 std  vector lt int gt  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 lt std  vector lt std  vector lt int gt  gt  gt  sub         return longestSubSeq     int getLongestIncSub const std  vector lt int gt   amp sequence        std  vector lt std  vector lt int gt  gt  sub      return getLongestIncSub sequence  sequence size   - 1  sub      int main         std  vector lt int gt  seq 0  8  2  3  7  9       std  cout  lt  lt  getLongestIncSub seq       return 0

User · Answer

Longest Increasing Subsequence Java   import java util     class ChainHighestValue implements Comparable lt ChainHighestValue gt       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 lt Integer gt  LongestSubsequent int arr    int size           ArrayList lt LinkedList lt Integer gt  gt  seqList new ArrayList lt  gt             ArrayList lt ChainHighestValue gt  valuePairs new ArrayList lt  gt             for int i 0 i lt size i                 int currValue arr i               if valuePairs size    0                   LinkedList lt Integer gt  aList new LinkedList lt  gt                     aList add arr i                    seqList add aList                   valuePairs add new ChainHighestValue arr i  1                  else                  try                      ChainHighestValue heighestIndex valuePairs stream   filter e- gt e highestValue lt 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 lt Integer gt  aList new LinkedList lt  gt                         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 lt Integer gt  LIS LongestSubsequent arry  arry length           System out println  Longest Incrementing Subsequence             for Integer a  LIS               System out print a

User · Answer

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 lt 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 lt n i                          dp i  1              String x                 for int j i-1 j gt  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  lt a i  amp  amp dp j  gt 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  gt 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

User · Answer

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  lt  i and check both if DP j    1  gt  DP i  and array j   lt  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  lt  N  i         DP i    1     prev i    -1      for  int j   i - 1  j  gt   0  j--        if  DP j    1  gt  DP i   amp  amp  array j   lt  array i                    DP i    DP j    1           prev i    j              if  DP i   gt  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    If X   last element in S  then append X to the end of S  This essentialy means we have found a new largest LIS  Otherwise find the smallest element in S  which is  gt   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    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  Otherwise find the index of the smallest element in S  which is  gt   than X  and change it to X  Here parent indexX    S index - 1

User · Answer

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  lt  arr length  i                  for  int j   0  j  lt  i  j                      if arr j  lt arr i   amp  amp    maxCount j  1  gt maxCount i                         maxCount i  maxCount j  1                      link i  j                      if maxCount i  gt maxCount maxI                            maxI i                                                                            for  int i   0  i  lt  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

User · Answer

Simplest LIS solution in C   with O nlog n   time complexity   include  lt iostream gt   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 lt int gt   amp a int beg int end int value        if beg lt  end                int mid    beg end  2          if a mid     value              return mid          else if value  lt  a mid               return ceilBinarySearch a beg mid-1 value           else             return ceilBinarySearch a mid 1 end value        return 0             return beg     int lis vector lt int gt  arr        vector lt int gt  dp arr size   0       int len   0      for int i   0 i lt 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 lt int gt  arr   2  5 -1 0 6 1 2       cout lt  lt lis arr       return 0      OUTPUT      4

[algorithm] How to determine the longest increasing subsequence using dynamic programming?

Examples related to algorithm

Examples related to computer-science

Examples related to dynamic-programming

Examples related to memoization

Examples related to lis