Find the largest sum such that no two elements are touching

Question

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 code-golf the shortest solution wins

Optional additional requirement:

• Your solution has to run in polynomial time (\$O(n^k)\$ for some integer k)

Answer 1

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

Answer 2

Haskell, 38 35 bytes

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!

Answer 3

R, 80 46 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.

Answer 4

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!

Try it online or verify all test cases.

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)

Answer 5

Befunge-98 (PyFunge), 35 52 60 67 bytes

1pp>1g00g`g3j>;#&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>1g00g`g3j>;#&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>1g00g`g3j>;#&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
           3j>;#&               ;.@  Jump to &, which gets one integer input.
                                     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

Answer 6

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

Answer 7

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)]:
     ⋅+           discard Mc and add Mn and Vi (arity 3)
       ↥          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

Answer 8

Vyxal G, 59 bits^v2, 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.

Answer 9

Charcoal, 21 bytes

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

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

Ｆ²⊞υ⁰

Start with an accumulator of two zeros.

ＦＡ

Loop over the input.

≔⟦⁺ι§υ¹⌈υ⟧υ

Update the accumulators.

Ｉ⌈υ

Output the best sum.

Answer 10

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

Answer 11

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!

Answer 12

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

Answer 13

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`

Answer 14

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.

Answer 15

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.

Answer 16

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!

Answer 17

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.

Answer 18

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!

Answer 19

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!

Answer 20

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!

Answer 21

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)

Answer 22

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)
}

Answer 23

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]));