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.
Programming Praxis 
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; }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:
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)
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:
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
@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
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
@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).
@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”
@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.
@programmingpraxis: Good points. Thanks for your efforts: They have provided many hours of enjoyment and learning.
Here’s a Haskell version. We take advantage of
Nothingbeing less thanJust xfor allx(assumingxis comparable). Also, the functiondivvyis such thatdivvy 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]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: