Local Maxima

February 16, 2021

A local maximum of a list of integers is an element of the list at which the adjacent list elements are either less than or equal to the current element; for instance, in the input list (1 2 1 2 3 4 3 2 3 2 1) there are three local maxima, one at the first 2, one at the 4, and one and the last 3. The elements at either end of a list should be considered as greater than the boundary. Only one maximum should be reported for a plateau (consecutive equal maxima).

Your task is to write a program that finds the local maxima of a list of integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: