## 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 if \$left < \$X && \$X > \$X;
\$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 - 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 if \$left < \$X && \$X > \$X;
\$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 
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,6]
[2,4,3]
```
13. Kevin said

A solution in Racket:

```;e: local maxima to be indicated in square brackets like so: (1  1 2 3  3 2  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  1 2 3  3 2  2 1)
> (local-maxima '(1 2 2 2 1))
(1 2 2  1)
> (local-maxima '(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  4 3 2 1  1 2 3  0 )
```