Jump to content

User:Nippashish

From Wikipedia, the free encyclopedia

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