# Find the largest sum such that no two elements are touching

Inspired by this (off topic) post

Given an array of numbers, find the largest sum over a subarray not containing two adjacent elements

[1,2,3,4]         -> 6   // [_,2,_,4]
[1,2,3,4,5]       -> 9   // [1,_,3,_,5]
[2,2,1,1,2,1,1,2] -> 7   // [2,_,1,_,2,_,_,2]
[3,1,4,1,5,9,2]   -> 16  // [3,_,4,_,_,9,_]
[9,8,7,9,9,8]     -> 26  // [9,_,_,9,_,8]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] -> 21


## Rules

• You can assume that all number in the array are positive integers
• This is the shortest solution wins

• Your solution has to run in polynomial time ($$\O(n^k)\$$ for some integer k)
• I suggest replacing "subset" by "subarray" and "consecutive" by "adjacent". I initially thought that order didn't matter ("subset") and that you meant no elements with values differing by 1 ("consecutive") Commented Sep 20, 2023 at 11:37
• I added a test case of 41 ones to catch exponential solutions.
– xnor
Commented Sep 20, 2023 at 20:08
• Any bonus points for handling negative numbers? Commented Sep 22, 2023 at 3:55
• This appears to be a close sibling of the partition problem which is NP complete; that would appear to make a truly general optimal polynomial-time solution impossible. Have I missed anything? (For example, consider the two sets [100,1,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,8] and [100,1,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,99,100,10] which have best sums of 1000 and 1001 respectively. Deciding to take the first 99 rather than the following 100 requires looking up to 100 elements further along.) Commented Sep 22, 2023 at 4:25
• @MartinKealey The look-ahead you describe in your example is not necessary when maintaining two sums while iterating over the list: one where the previous element has been added (corresponding to sum[..., _, x]), and one where it was omitted (sum[..., _]). See O B's answer. Commented Sep 22, 2023 at 13:51

# Ruby, 46 38 bytes

->l{a=b=0;l.map{a,b=b,[a+_1,b].max};b}


Attempt This Online! Runs in O(n).

### How?

We need 2 accumulators. The first 2 steps will initialize them with the first 2 elements of the list. Then at every step: add the current element to the accumulator that was not increased in the previous step, and discard the smallest.

### Example:

[3,1,4,1,5,9,2]
Start -> a=0, b=0
3     -> a=0, b=3
1     -> a=3, b=1
4     -> a=3, b=[3+_+4]
1     -> a=[3+_+4], b=[3+_+_+1]
5     -> a=[3+_+4], b=[3+_+4+_+5]
9     -> a=[3+_+4+_+5], b=[3+_+4+_+_+9]
2     -> a=[3+_+4+_+_+9], b=[3+_+4+_+5+_+2]


Thnks @tsh for -6 bytes

• 35 bytes
– att
Commented Oct 19, 2023 at 7:30

g(x:y:r)=max(g$y:r)$x+g r
g x=sum x


Attempt This Online!

g x=sum x is a handy way to combine the two base cases g[x]=x and g[]=0.

# Haskell, $$\O(n)\$$, 42 38 bytes

fst.foldr(\a(b,c)->(max(a+c)b,b))(0,0)


Attempt This Online!

Based on G B's Ruby answer. -4 bytes thanks to regr4444!

• Nice answer. What is the complexity of the first solution? Commented Sep 20, 2023 at 15:00
• @Jonah It looks like it should be Fibonacci, so roughly $\phi^n$.
– xnor
Commented Sep 21, 2023 at 5:16
• I'm fairly sure that fst.foldr(\a(b,c)->(max(a+c)b,b))(0,0) should also work as an O(n) solution Commented Nov 10, 2023 at 20:10

# R, 8046 43 bytes

Edit: hugely golfed with inspiration from G B's answer: upvote that!

\(x)max(Reduce(\(a,i)c(max(a),a[1]+i),x,0))


Attempt This Online!

Runs in polynomial time.

# 05AB1E, 11 8 bytes

ÎĆvMsy+s


-3 bytes and $$\O(n)\$$ complexity by porting @G B's Ruby answer, so make sure to upvote that answer as well!

Explanation:

Î        # Push 0 and the input-list
Ć       # Enclose; append the first item at the end of the input-list
# (this is to have an extra iteration, the value that's appended is irrelevant)
v      # Pop and loop over each item y of this modified input-list:
M     #  Push a copy of the stack's maximum
s    #  Swap so the previous value (or 0 in the first iteration) is at the top again
y+  #  Add the current loop-integer y to it
s #  Swap back to the pushed maximum for the next iteration
# (after the loop, the maximum of the extra iteration is output implicitly)


# Befunge-98 (PyFunge), 35 526067 bytes

1pp>1g00gg3j>;#&00g+01p00p'#j<;.@


Try it online!
Takes input as a series of space separated integers. The last integer must have a trailing space.

Uses the dynamic programming approach, and so runs in O(n).

### Alternate version with only printable characters, 36 bytes

1pp>1g00gg3j>;#&00g+01p00p93*#j<;.@


Try it online!
Same as above but replaces the unprintable character with 9*3=27, costing an extra byte (which is why it is not 26)

## Explanation

Here the unprintable character has been replaced by O. Note that the unprintable character has ASCII value of 26

1pp>1g00gg3j>;#&00g+01p00p'O#j<;.@  Full program
1p                                   0 is always on the stack, so 1p stores 0
at (0,1)
p                                  stores 0 at (0,0)
>         >;#&          'O#j<;.@  Loop until EOF received
1g00g                            Get (0,1) and put on stack, then get
(0,0) and put on stack
Pop b, then a, push 1 if a>b, otherwise
push 0
g                          Stack now either contains 1 or 0, which
corresponds to one of the stored values,
get that value
If EOF, print top of the stack, then end
Otherwise if continuing loop:
00g+                Get (0,0) then add top two values of
the stack
01p00p          Pop the top of the stack and store at
(0,1), then get the top of the stack
again and store at (0,0)
'O#j<     Jump 26 characters back to the start of
the loop


# JavaScript (ES6), 43 bytes

Port of GB's answer, running in $$\O(n)\$$.

a=>[...a,b=0].map(v=>[b,a]=[a>b?a:b,b+v])|b


Try it online!

# JavaScript (ES6), 44 bytes

This one runs in $$\O(2^n)\$$.

f=([v,...a],p)=>x=v?p|(v+=f(a,1))<f(a)?x:v:0


Try it online!

### Commented

f = (        // f is a recursive function taking:
[v,        //   v = next value from the input array
...a], //   a[] = remaining values
p          //   p = flag set if the previous value was used
) =>         //
x =          // save the result in x
v ?          // if v is defined:
p | (      //   if p is set
v +=     //   or the updated value of v obtained by adding
f(a, 1)  //   the result of a recursive call with p set
) < f(a) ? //   is less than f(a):
x        //     use x (the result of f(a))
:          //   else:
v        //     use v
:            // else:
0          //   stop


# Uiua, 8 bytes

↥∧⊃⋅+↥.0


Try it online!

↥∧⊃⋅+↥.0    input: a vector V of numbers
.0    set up two accumulators:
maximum containing the last element (Mc),
maximum not containing the last element (Mn)
∧          fold over V: for each item Vi,
⊃⋅+↥        replace [Mc Mn Vi] with [Mn+Vi max(Mc,Mn)]:
↥          max of Mc and Mn (arity 2)
⊃             fork: take 3 values and pass enough amount of args to each function
↥             max of final Mc and Mn


# VyxalG, 59 bitsv2, 7.375 bytes

ẏṗ'¯‹g;İṠ


Try it Online!

Probably doesn't meet the criteria of running in polynomial time.

## Explained

ẏṗ'¯‹g;İṠ­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁪‏‏​⁡⁠⁡‌⁢​‎⁪⁪⁠⁪⁪⁠‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌⁤​‎‏​⁢⁠⁡‌⁢⁡​‎‏​⁢⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁢⁤⁪‏‏​⁡⁠⁡‌⁢⁣​‎‎⁪⁡⁪⁠⁪⁣⁡⁪‏‏​⁡⁠⁡‌⁢⁤​‎‏​⁢⁠⁡‌­
ẏṗ'   ;    # ‎⁡Keep items of the powerser of range(0, len(input)) where:
g     # ‎⁢ The minimum
¯‹      # ‎⁣  Of deltas - 1 isn't 0
# ‎⁤Essentially, this finds all sets without consecutive items, as consecutive items will have a forwards difference of 1, which is 0 when decremented.
# ‎⁢⁡This works regardless of input because it's operating on the list of indices, not actual values
İ   # ‎⁢⁢Index into the input list
Ṡ  # ‎⁢⁣And sum each
# ‎⁢⁤The G flag outputs the biggest sum
💎


Created with the help of Luminespire.

• "powerset of range(0, len(input))" takes $\mathcal{O}(2^n)$ time, so this is not valid. Commented Oct 16, 2023 at 6:03
• @Bubbler - note that running in polynomial time was described as an 'optional additional requirement'. Commented Oct 16, 2023 at 7:09
• @DominicvanEssen Oops, sorry. I was misled by the restricted-complexity tag and didn't read the text carefully. Commented Oct 16, 2023 at 7:16

# Charcoal, 21 bytes

Ｆ²⊞υ⁰ＦＡ≔⟦⁺ι§υ¹⌈υ⟧υＩ⌈υ


Try it online! Link is to verbose version of code. Explanation: Port of @GB's Ruby answer.

Ｆ²⊞υ⁰


ＦＡ


Loop over the input.

≔⟦⁺ι§υ¹⌈υ⟧υ


Update the accumulators.

Ｉ⌈υ


Output the best sum.

# Nibbles, 9.5 bytes (19 nibbles)

//$,1:/@]+/@$$]  Attempt This Online! Runs in polynomial time. Direct port of my R answer, which is itself inspired by G B's answer.  / # fold from right$                # over the input,
,1             # starting with a list of only [0]:
:            #   join
/@]         #     maximum in the result-list-so-far
#   to
/@$# first entry of the result-list-so-far +$    #     plus the current element
/              ]   # and output get the maximum in the final result-list


# Scala 3, 69 bytes

l=>{val(a,b)=l.foldLeft((0,0)){case((a,b),c)=>(a max b,a+c)};a max b}


Attempt This Online!

# JavaScript (Node.js), 39 bytes

a=>a.map(v=>q=(v+=p)>(p=q)?v:p,p=q=0)|q


Try it online!

Use two variables p, and q to track:

• p: Largest sum we got for a[0..i-1]
• q: Largest sum we got for a[0..i]

So, for each iteration,

• i' = i + 1
• p' = q
• q' = max(q, p + a[i'])

# Java, 64 57 bytes

a->{int t=0,r=0;for(int k:a)r=(k+=t)>(t=r)?k:t;return r;}


Another port of @G B's Ruby answer.
Also runs in $$\O(n)\$$ complexity.

Try it online.

Explanation:

a->{                    // Method with integer-array parameter and integer return-type
int t=0,              //  Temp-integer, starting at 0
r=0;              //  Result-integer, starting at 0 as well
for(int k:a)          //  Loop over the integers k of the input-array:
r=(k+=t)>(t=r)?k:t;
//  (k+=t)            //   First increase the current k by value t
//         (t=r)      //   Then replace t with value r
//r= k    > t   ?k:t; //   And then set r to the maximum of these new k and t as
//   preparation for the next iteration
return r;}            //  After the loop, return the final 'prepared' maximum r


# Python, 48 bytes

lambda a,b=0,c=0:max(b:=max(d+c,c:=b)for d in a)


Attempt This Online!

$$\O(n)\$$ complexity.

Loops over the list. On each prefix, b and c are the largest such sums of the two previous prefixes.

# Retina 0.8.2, 41 bytes

.+
$* +^((.+).*)¶\2(.*)¶$1$3¶$1
O^
\G1


Try it online! Takes input on separate lines but link is to test suite that splits on commas for convenience. Explanation: Another port of @GB's Ruby answer.

.+
$*  Convert to unary. +^((.+).*)¶\2(.*)¶$1$3¶$1


Add the first element to the third and keep the larger of the first and second elements.

O^


Sort descending.

\G1


Convert the larger of the remaining two numbers to decimal.

# JavaScript (Node.js), 47 bytes

x=>x.map(e=(t,i)=>e=x[i]=(t+=~~x[i-2])<e?e:t)|e


Try it online!

# Python, 55 bytes

f=lambda a,b,c,*d:d and f(max(a,b),a+c,*d)or max(a+c,b)


Attempt This Online!

Adapted from G B's answer. It only works if the array is at least three elements long.

# C (clang), $$\\mathcal{O}(N)\$$, 53 bytes

takes in a zero-terminated array of positive integers and returns via out parameter.

n,t;f(*a,*r){for(*r=n=0;*a;(n=*r)<t?*r=t:0)t=n+*a++;}


Try it online!

# C (gcc), $$\\mathcal{O}(N)\$$, 46 bytes

This one returns the result in the first element of the array, has UB in the form of unsequenced modification and access to a[2] and requires the last two elements of the array to be $$\0\$$.

f(int*a){*a=*a?f(a+1)<a[2]+*a?a[2]+*a:a[1]:0;}


Try it online!

# Erlang, 77 bytes

f(L)->f(L,{0,0}).
f([],{A,B})->max(A,B);
f([H|T],{A,B})->f(T,{max(A,B),A+H}).


Attempt This Online!

# Elixir, 80 bytes

def f(l)do
{a,b}=Enum.reduce(l,{0,0},fn x,{a,b}->{max(a,b),a+x}end)
max(a,b)
end


Attempt This Online!

# Racket, 99 bytes

Golfed version. Try it online!

(define (f l)(let loop([l l][a 0][b 0])(if (null? l)(max a b)(loop(cdr l)(max a b)(+ a (car l))))))


Ungolfed version. Try it online!

#lang racket

(define (max_sum lst)
(let loop ([lst lst] [a 0] [b 0])
(if (null? lst)
(max a b)
(loop (cdr lst) (max a b) (+ a (car lst))))))

(define (main)
(displayln (max_sum '(1 2 3 4)))
(displayln (max_sum '(1 2 3 4 5)))
(displayln (max_sum '(2 2 1 1 2 1 1 2)))
(displayln (max_sum '(3 1 4 1 5 9 2)))
(displayln (max_sum '(9 8 7 9 9 8))))

(main)


# Rust, 90 bytes

Golfed version. Try it online!

fn s(a:Vec<i32>)->i32{let(x,y)=a.into_iter().fold((0,0),|(x,y),z|(x.max(y),x+z));x.max(y)}


Ungolfed version. Try it online!

fn main() {
println!("{}", max_sum(vec![1,2,3,4]));
println!("{}", max_sum(vec![1,2,3,4,5]));
println!("{}", max_sum(vec![2,2,1,1,2,1,1,2]));
println!("{}", max_sum(vec![3,1,4,1,5,9,2]));
println!("{}", max_sum(vec![9,8,7,9,9,8]));
}

fn max_sum(arr: Vec<i32>) -> i32 {
let (a, b) = arr.into_iter().fold((0, 0), |(a, b), c| (std::cmp::max(a, b), a + c));
std::cmp::max(a, b)
}


# OCaml, 104 bytes

Golfed version. Try it online!

let rec m l=match l with []->0|x::xs->let(a,b)=List.fold_left(fun(a,b)x->(max a b,a+x))(0,0)l in max a b


Ungolfed version. Try it online!

let rec max_sum lst =
let rec helper (a, b) = function
| [] -> max a b
| h::t -> helper (max a b, a + h) t
in helper (0, 0) lst

let () =
print_endline (string_of_int (max_sum [1; 2; 3; 4]));
print_endline (string_of_int (max_sum [1; 2; 3; 4; 5]));
print_endline (string_of_int (max_sum [2; 2; 1; 1; 2; 1; 1; 2]));
print_endline (string_of_int (max_sum [3; 1; 4; 1; 5; 9; 2]));
print_endline (string_of_int (max_sum [9; 8; 7; 9; 9; 8]));
`