23
\$\begingroup\$

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

Optional additional requirement:

  • Your solution has to run in polynomial time (\$O(n^k)\$ for some integer k)
\$\endgroup\$
6
  • 7
    \$\begingroup\$ 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") \$\endgroup\$
    – Luis Mendo
    Sep 20, 2023 at 11:37
  • \$\begingroup\$ I added a test case of 41 ones to catch exponential solutions. \$\endgroup\$
    – xnor
    Sep 20, 2023 at 20:08
  • \$\begingroup\$ Any bonus points for handling negative numbers? \$\endgroup\$ Sep 22, 2023 at 3:55
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ Sep 22, 2023 at 4:25
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – Laikoni
    Sep 22, 2023 at 13:51

23 Answers 23

24
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ 35 bytes \$\endgroup\$
    – att
    Oct 19, 2023 at 7:30
10
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ Nice answer. What is the complexity of the first solution? \$\endgroup\$
    – Jonah
    Sep 20, 2023 at 15:00
  • 1
    \$\begingroup\$ @Jonah It looks like it should be Fibonacci, so roughly \$\phi^n\$. \$\endgroup\$
    – xnor
    Sep 21, 2023 at 5:16
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – regr4444
    Nov 10, 2023 at 20:10
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Vyxal G, 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.

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

Charcoal, 21 bytes

F²⊞υ⁰FA≔⟦⁺ι§υ¹⌈υ⟧υI⌈υ

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

F²⊞υ⁰

Start with an accumulator of two zeros.

FA

Loop over the input.

≔⟦⁺ι§υ¹⌈υ⟧υ

Update the accumulators.

I⌈υ

Output the best sum.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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'])
\$\endgroup\$
3
\$\begingroup\$

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`
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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)
}
\$\endgroup\$
0
\$\begingroup\$

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]));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.