Local Maxima

February 16, 2021

We keep track of both the previous element and the current direction, either climbing up or falling down, and compute the maxima in a single scan of the list:

(define (lmax xs)
   (if (null? xs) (error 'lmax "empty")
     (let loop ((xs (cdr xs)) (prev (car xs)) (dir 'up) (maxs (list)))
       (cond ((null? xs)
               (reverse (if (equal? dir 'up) (cons prev maxs) maxs)))
             ((= prev (car xs)) (loop (cdr xs) prev dir maxs))
             ((< prev (car xs)) (loop (cdr xs) (car xs) 'up maxs))
             ((equal? dir 'up) (loop (cdr xs) (car xs) 'down (cons prev maxs)))
             (else (loop (cdr xs) (car xs) 'down maxs))))))

Here is the sample problem:

> (lmax '(1 2 1 2 3 4 3 2 3 2 1))
(2 4 3) 

You can run the program at https://ideone.com/RduLyR.

Pages: 1 2

13 Responses to “Local Maxima”

  1. James Curtis-Smith said

    Perl version…

    say join ' ', maxima( qw(1 2 1 2 3 4 3 2 3 2 1) );
    sub maxima {
      my @X = @_;
      push @X, my $left = -1e32;
      my @sol;
       while(@X>1) {
        push @sol,$X[0] if $left < $X[0] && $X[0] > $X[1];
        $left = shift @X;
      }
      return @sol;
    }
    
  2. Daniel said

    Here’s a solution in Python. It’s not particularly efficient, as it creates multiple copies of the input list.

    from itertools import groupby
    
    def local_maxima(l):
        assert len(l) > 0, 'Input can\'t be empty'
        # Remove adjacent duplicates and add boundary elements
        l = [l[0] - 1] + [x for x, _ in groupby(l)] + [l[-1] - 1]
        return [y for x, y, z in zip(l, l[1:], l[2:]) if x < y and y > z]
    
    l = [1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1]
    print(local_maxima(l))
    

    Output:

    [2, 4, 3]
    
  3. Steve said

    Cache version

    [sourcecode lang="css"]

    test ;
    q
    ;
    localmaxima(list) ; Output local maxima
    n i,next,previous,this
    s list=$e(list)-1_” “list” “($e(list,$l(list)-1)-1)
    s output=””
    f i=2:1:$l(list,” “)-1 {
    s this=$p(list,” “,i),previous=$p(list,” “,i-1),next=$p(list,” “,i+1)
    i this>previous, this>next s output=output_this
    ” ”
    }
    q $e(output,1,$l(output)-1)

    s list=”1 2 1 2 3 4 3 2 3 2 1″
    w !,list,!,$$localmaxima(list)
    1 2 1 2 3 4 3 2 3 2 1
    2 4 3

  4. chaw said

    Here is a solution in a somewhat functional style using standard R7RS
    Scheme and a few well-known helpers form SRFI 1. It provides both
    values and locations of the local maxima.

    (import (scheme base)
            (only (srfi 1)
                  circular-list filter-map iota) 
            (scheme write))
    
    (define samples ; ((input . output) ...)
      '(((1 2 1 2 3 4 3 2 3 2 1) . (1 5 8))
        (() . ())
        ((1) . (0))
        ((1 1) . (0))
        ((7 7 7) . (0))
        ((7 6 7) . (0 2))
        ((7 7 6 7) . (0 3))
        ((7 7 7 7 6 7) . (0 5))
        ((7 7 7 7 6 7 7) . (0 5))
        ((7 7 5 5 6 7 7 6 7 5 7) . (0 5 8 10))
        ((7 7 5 5 6 7 7 6 7 5 7 7) . (0 5 8 10))
        ((7 7 5 5 6 7 7 6 7 5 7 6) . (0 5 8 10))))
    
    ;; nums -> ((lmax-val lmax-idx) ...)
    (define (local-maxima nums)
      (let* ((xs (apply circular-list -inf.0 nums))
             (ys (cdr xs))
             (zs (cdr ys))
             (yi (iota (length nums))))
        ;; x, y, z are consecutive nums with -inf.0 as sentinel at both ends
        (filter-map (lambda (x y z i)
                      ;; is y a local maximum, leftmost in case of plateau?
                      (and (< x y)
                           (<= z y)
                           (list y i)))
                    xs
                    ys
                    zs
                    yi)))
    
    (define (local-maxima-values nums)
      (map car (local-maxima nums)))
    
    (define (local-maxima-indexes nums)
      (map cadr (local-maxima nums)))
    
    (define (demo)
      (display (equal? (map cdr samples)
                       (map local-maxima-indexes (map car samples))))
      (newline))
    
    (demo)
    

    Output:

    #t
    

  5. Cache version – Fix formatting

    
    test ;
      q
    ;
    localmaxima(list) ; Output local maxima
      n i,next,previous,this
      s list=$e(list)-1_” “list” “($e(list,$l(list)-1)-1)
      s output=””
      f i=2:1:$l(list,” “)-1 {
        s this=$p(list,” “,i),previous=$p(list,” “,i-1),next=$p(list,” “,i+1)
        i this>previous, this>next s output=output_this” ”
      }
      q $e(output,1,$l(output)-1)
    
    

    s list=”1 2 1 2 3 4 3 2 3 2 1″
    w !,list,!,$$localmaxima(list)
    1 2 1 2 3 4 3 2 3 2 1
    2 4 3

  6. @James Curtis-Smith

    I’m unfamiliar with Perl. I tried typing your program into a file and executing it:

    $ perl -e localmaxima.pl

    Steve@DESKTOP-0SFLH1S MINGW64 ~/Desktop
    $ perl -E localmaxima.pl

    Steve@DESKTOP-0SFLH1S MINGW64 ~/Desktop
    $ perl localmaxima.pl
    syntax error at localmaxima.pl line 1, near “say join”
    Execution of localmaxima.pl aborted due to compilation errors.

    I also tried typing it into the interpreter, but couldn’t figure out how to execute it.

    Any tips?

    Thanks, Steve

  7. Changed the program (localmaxima.pl) to the following, and executing “./localmaxima.pl” returned the expected values:
    #!/usr/bin/perl
    print join ‘ ‘, maxima( qw(1 2 1 2 3 4 3 2 3 2 1) );
    sub maxima {
    my @X = @_;
    push @X, my $left = -1e32;
    my @sol;
    while(@X>1) {
    push @sol,$X[0] if $left < $X[0] && $X[0] > $X[1];
    $left = shift @X;
    }
    return @sol;
    }

    Sure enjoy learning new languages and seeing new solutions.

    Thanks, all.

    Steve

  8. programmingpraxis said

    @James Curtis-Smith and @bookofstevegraham: What do your programs return when given (1 3 3 1) as input? They should return a local maximum of (3).

  9. @programmingpraxis: Good catch – Didn’t know you read Cache/Mumps! I was allowing for mountain peaks as maxima, but not buttes.

    Revised program and tests

    
    >zl test zp  s qt="""" for list="1 2 1 2 3 4 3 2 3 2 1","1 3 3 1","","1","1 1","7 7 7","7 6 7","7 7 6 7","7 7 7 7 6 7","7 7 7 7 6 7 7","7 7 5 5 6 7 7 6 7 5 7","7 7 5 5 6 7 7 6 7 5 7 7", "7 7 5 5 6 7 7 6 7 5 7 6" w !!,qt,list,qt,!,qt,$$localmaxima^test(list),qt
    
    test         ;
                     q
                     ;
    localmaxima(list) ; Output local maxima
                     n i,next,previous,this
                     s list=$e(list)-1_" "_list_" "_($e(list,$l(list)-1)-1),output=""
                     f i=2:1:$l(list," ")-1 {
                      s this=$p(list," ",i),previous=$p(list," ",i-1),next=$p(list," ",i+1)
                      i this>previous,this'<next s output=output_this_" "
                     }
                     q $e(output,1,$l(output)-1)
     
     

    “1 2 1 2 3 4 3 2 3 2 1”
    “2 4 3”

    “1 3 3 1”
    “3”

    “”
    “”

    “1”
    “1”

    “1 1”
    “1”

    “7 7 7”
    “7”

    “7 6 7”
    “7 7”

    “7 7 6 7”
    “7 7”

    “7 7 7 7 6 7”
    “7 7”

    “7 7 7 7 6 7 7”
    “7 7”

    “7 7 5 5 6 7 7 6 7 5 7”
    “7 7 7 7”

    “7 7 5 5 6 7 7 6 7 5 7 7”
    “7 7 7 7”

    “7 7 5 5 6 7 7 6 7 5 7 6”
    “7 7 7 7”

  10. programmingpraxis said

    @bookofstevegraham: Actually, I don’t speak cache/mumps. but it’s not too hard to figure out that you have a statement “if this > previous and this > next then output this” which handles peaks but not plateaus.

    The problem is my fault, not yours. The description mentions plateaus, but not clearly, and I didn’t give an example of an input that contains plateaus. If my example had been (1 2 1 2 3 4 3 2 3 3 3 2 1) the situation would have been obvious.

  11. @programmingpraxis: Good points. Thanks for your efforts: They have provided many hours of enjoyment and learning.

  12. Globules said

    Here’s a Haskell version. We take advantage of Nothing being less than Just x for all x (assuming x is comparable). Also, the function divvy is such that divvy 3 1 [1..5] equals [[1,2,3],[2,3,4],[3,4,5]].

    import Data.List (group)
    import Data.List.Split (divvy)
    import Data.Maybe (mapMaybe)
    
    locmax :: Ord a => [a] -> [a]
    locmax xs = map head $ group $ mapMaybe midMax $ divvy 3 1 ys
      where ys = [Nothing] ++ map Just xs ++ [Nothing]
            midMax [x, y, z] = if x <= y && y >= z then y else Nothing
    
    main :: IO ()
    main = do
      print $ locmax ([] :: [()])
      print $ locmax [5]
      print $ locmax [5, 4]
      print $ locmax [5, 6]
      print $ locmax [5, 5, 5, 6, 6]
      print $ locmax [1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1]
    
    $ ./locmax
    []
    [5]
    [5]
    [6]
    [5,6]
    [2,4,3]
    
  13. Kevin said

    A solution in Racket:

    ;e: local maxima to be indicated in square brackets like so: (1 [2] 1 2 3 [4] 3 2 [3] 2 1)
    (define (loc-max input)
      (foldl (λ (val init)
               (let ((last (car init)) (next (if (null? (cdadr init)) null (cadadr init))))
                 (let ((tmp (if (and (or (null? last) (<= last val)) (or (null? next) (< next val))) "[~a]" "~a")))
                   (list val (cdadr init) (cons (format tmp val) (caddr init))))))
             (list null input null)
             input))
    
    (define (local-maxima input)
      (display (string-join (reverse (caddr (loc-max input))) #:before-first "(" #:after-last ")")))
    

    Examples:

    > (local-maxima '(1 2 1 2 3 4 3 2 3 2 1))
    (1 [2] 1 2 3 [4] 3 2 [3] 2 1)
    > (local-maxima '(1 2 2 2 1))
    (1 2 2 [2] 1)
    > (local-maxima '(1))
    ([1])
    > (local-maxima '())
    ()
    > (local-maxima '(1 2 3 4 5 4 3 2 1 2 1 2 3 46 0 3))
    (1 2 3 4 [5] 4 3 2 1 [2] 1 2 3 [46] 0 [3])
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: