Dots

edit
 

...


 

...

 

Not solvable when:

 

Monotonically Increasing

edit

Given a sequence of n numbers:

 

Want to find the longest monotonically increasing subsequence.

Define the function   as the length of the longest monotonically increasing subsequence in the first n elements.

 

Algorithm

edit

Algorithm MonotonicIncrease(S, n)
Input
  S - A sequence of numbers  .
  n - The length of the sequence S.
Output
  A monotonically increasing subsequence of S of maximal length.
Begin
  L <- An array of n integers with L[k] is the length of the longest monotonic 
       subsequence in  .
  D <- An array of n integers where D[k] holds the index of the previous
       number in the longest monotonic sequence in  
       ending with  .  Initially filled with 0's.

  // Build the dynamic program 
  L[1] <- 1
  for  
    longest <- 0
    for  
      if  
        if  
          longest <- j
    D[i] <- longest
    L[i] <- L[longest] + 1

  // Find the endpoint of the longest sequence
  f <- 1
  for  
    if  
      f <- i

  // Print the solution
  PrintMonotonicIncrease(S, D, f)
End
Algorithm PrintMonotonicIncrease(S, D, f)
Input
  S - A sequence of numbers  .
  D - An array of n integers where D[k] holds the index of the previous
      number in the longest monotonic sequence in  
      ending with  .
  f - The index of the final integer in the solution.
Output
  The optimal sequence.
Begin
  if  
    PrintMonotonicIncrease(S, D, D[f])
    print S[f]
End

Test Work

edit

Try this out...

 

o---o---o---o---o---o---o---o
| 1 | 4 | 2 | 7 | 8 | 4 | 5 |
o---o---o---o---o---o---o---o
| 1 | 2 | 2 | 3 | 4 | 4 | 4 |
o---o---o---o---o---o---o---o

And this...

 

o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14|
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 | 3 | 3 | 7 | 2 | 6 | 4 | 5 | 6 | 1 | 8 | 3 | 2 | 6 |
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o
| 1 |1 2|2 3|3 4|1 2|3 4|3 4|7 5|8 6|1 2|9 7|3 4|5 3|9 7|
o---o---o---o---o---o---o---o---o---o---o---o---o---o---o