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