How to resolve the algorithm Longest increasing subsequence step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Longest increasing subsequence step by step in the Racket programming language

Table of Contents

Problem Statement

Calculate and show here a longest increasing subsequence of the list: And of the list: Note that a list may have more than one subsequence that is of the maximum length.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Longest increasing subsequence step by step in the Racket programming language

Source code in the racket programming language

#lang racket/base
(require data/gvector)

(define (gvector-last gv)
  (gvector-ref gv (sub1 (gvector-count gv))))

(define (lis-patience-sort input-list)
  (let ([piles (gvector)])
    (for ([item (in-list input-list)])
      (insert-item! piles item))
    (reverse (gvector-last piles))))
 
(define (insert-item! piles item)
  (if (zero? (gvector-count piles))
      (gvector-add! piles (cons item '()))
      (cond
        [(not (<= item (car (gvector-last piles))))
         (gvector-add! piles (cons item (gvector-last piles)))]
        [(<= item (car (gvector-ref piles 0)))
         (gvector-set! piles 0 (cons item '()))]
        [else (let loop ([first 1] [last (sub1 (gvector-count piles))])
                (if (= first last)
                    (gvector-set! piles first (cons item (gvector-ref piles (sub1 first))))
                    (let ([middle (quotient (+ first last) 2)])
                      (if (<= item (car (gvector-ref piles middle)))
                          (loop first middle)
                          (loop (add1 middle) last)))))])))

You may also check:How to resolve the algorithm Holidays related to Easter step by step in the Fortran programming language
You may also check:How to resolve the algorithm Smith numbers step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Draw a cuboid step by step in the Scala programming language
You may also check:How to resolve the algorithm Plot coordinate pairs step by step in the Raku programming language
You may also check:How to resolve the algorithm Set consolidation step by step in the PL/I programming language