## 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'
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)

(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 ((tmp (if (and (or (null? last) (<= last val)) (or (null? next) (< next val))) "[~a]" "~a")))
(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])