[Question]
  [
*Inspired by [this](https://codegolf.stackexchange.com/questions/265087/dp-approach-gives-tle) (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](/questions/tagged/code-golf "show questions tagged '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]
# [Ruby](https://www.ruby-lang.org/), ~~46~~ 38 bytes
```
->l{a=b=0;l.map{a,b=b,[a+_1,b].max};b}
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72kqDSpcsGiNNulpSVpuhY31XTtcqoTbZNsDaxz9HITC6oTdZJsk3SiE7XjDXWSYoFCFbXWSbVQ1XEFCmnR0YY6RjrGOiaxsVzIXB1TmIARUMBQxxBGwoSNgRwTIDbVsUQIWupY6JgDBYB0bCzElgULIDQA)
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]
# [Haskell](https://www.haskell.org), ~~38~~ 35 bytes
```
g(x:y:r)=max(g$y:r)$x+g r
g x=sum x
```
[Attempt This Online!](https://ato.pxeger.com/run?1=TZBLCsIwEIYRXPUUA3bR4tSSPqwR6g08QSmlC43FRkpViGdx40Y8k57GiWnUwDyS__uHMNfHrj7uN217u93Pp22weE6Ep5aXZe_nslaecHXrqqmA3hGg8uNZgjLoazR2ZN0cIAdZd2vwur45nGbCh8KBgmGEMSYlgj1BAMEK5tSFIRQV6RXpPxTTL2xQPqCMwJgi1XBEMENmM1kMnA2wnqoNulLWlpgeEooU-cdg57O5sejZyQfnWGkDxwVmdKFaln8figYDtzDpjlmG3d8b)
`g x=sum x` is a handy way to combine the two base cases `g[x]=x` and `g[]=0`.
---
# [Haskell](https://www.haskell.org), \$O(n)\$, ~~42~~ 38 bytes
```
fst.foldr(\a(b,c)->(max(a+c)b,b))(0,0)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=TZBdisIwEIDZFx96inmSBCdq-qdB9AaeoJaSqtViq6IVhGVP4ktBxDPtnmYnpnU3MDNJ5vuGkNtzq8-7dVHU98_N9HGpMjH-7mbnqp8ditWJLTRLccnFjJX6ynRvyVNMOWdDHHJL_3x0Jk6p8z1ModTHObDjKd9X_Q2HyIFIoose-jFCu4QAMYOQdoMBRAn1E-r_oRi8YYuqBpUEehSBgV2CJco2k2LhUQObqUYwlbJRPLrwKQJUL6GdL0OrmNn-C1eYGEHhGEd0oBrH_x7kNoJqYeo7X_Y76trWXw)
Based on [G B's Ruby answer](https://codegolf.stackexchange.com/a/265384/56433). -4 bytes thanks to [regr4444](https://codegolf.stackexchange.com/users/95913/regr4444)!
[Answer]
# [R](https://www.r-project.org), ~~80~~ ~~46~~ 43 bytes
*Edit: hugely golfed with inspiration from [G B's answer](https://codegolf.stackexchange.com/a/265384/95126): upvote that!*
```
\(x)max(Reduce(\(a,i)c(max(a),a[1]+i),x,0))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=TY9LDsIgEED3noLEDZNOU2nph4Uewm3bNKTapAs3xia9i5tq4qG8hwdw6ICRZBgY3hvg_rguz2H_mm5DXL2jRs5wsbM8nk9Tf5aNtDhCL13JAtpatdEIOOMOwCufQfZSYYoZagARxlbEByEKWiWJqDs671C3mz8Y8x_OsPGwIjSjyBlPCVeowkwS46XHXWenuEwzSxmVNEWOZlXCHapgyfXXq2CwY8VghSVtKfuHsZJ6xQQcq5b_viycvw)
Runs in polynomial time.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~11~~ 8 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
√éƒÜvMsy+s
```
-3 bytes and \$O(n)\$ complexity by porting [*@G B*'s Ruby answer](https://codegolf.stackexchange.com/a/265384/52210), so make sure to upvote that answer as well!
[Try it online](https://tio.run/##yy9OTMpM/f//cN@RtjLf4krt4v//ow11jHSMdUx0TGMB) or [verify all test cases](https://tio.run/##S0oszvifnFiiYKeQnJ@SqpdfnJiUmapgY6Pg6u/GZa@k8KhtkoKS/f/DfUfaynyLK7WL/9fqcIHkuMozMnNSFYpSE1MUMvO4UvK5FBT08wtK9CFGQCk0U20UVMBq81L/RxvqGOkY65jEcsFYOqZAthGQbahjCCOBIsZA2gSITXUswXxLHQsdcyAbSMdyAQA).
**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]
# [Befunge-98 (PyFunge)](https://pythonhosted.org/PyFunge/), 35 ~~52~~ ~~60~~ ~~67~~ bytes
```
1pp>1g00g`g3j>;#&00g+01p00p'#j<;.@
```
[Try it online!](https://tio.run/##S0pNK81LT9W1tNAtqAQz//83LCiwM0w3MEhPSDfOsrNWVgMytQ0MCwwMCtSllLNsrPUc/v@3VLBQMFewVADRAA "Befunge-98 (PyFunge) ‚Äì 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!](https://tio.run/##S0pNK81LT9W1tNAtqAQz//83LCiwM0w3MEhPSDfOsrNWVgMytQ0MCwwMCiyNtZSzbKz1HP7/t1SwUDBXsFQA0QA "Befunge-98 (PyFunge) ‚Äì 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]
# JavaScript (ES6), 43 bytes
Port of [GB's answer](https://codegolf.stackexchange.com/a/265384/58563), running in \$O(n)\$.
```
a=>[...a,b=0].map(v=>[b,a]=[a>b?a:b,b+v])|b
```
[Try it online!](https://tio.run/##bc7dCsIgFAfw@57Cy41OLveZgetBRIauLYo1R4td9e52rEbBEs454N8fx4ue9FjfzsN909tj41rhtCglpVSDEVtFr3oIJrwxoJWQujQHvTdg1pMKH8bVth9t19DOnoI2kAxiSCBV5HPCkEQRyQmRFSYVJqv/AjL1KzgKhu8TrGxhYjQM2NzV2xRo/A7v/MS@kAmmKVYGHNN5G8uJ9JvSl@JQLRyHHRSY4FTfX8bo@GwwcU8 "JavaScript (Node.js) ‚Äì 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!](https://tio.run/##bc7NCsIwDAfwu0/RY4uxs/u0w7oHGWWM6UQZ63BSdvDda6oOhVlIcvj3R3KtbT02t8tw3/TmeHKuVbS0wDmvNQxMHSZli@FB7Vq1tAbB2B4nK6bc5lvXmH403Yl35kxbWgoIIYJYk89jjAQBSQkpK0wqTFb/BST6V0gUAv9HWMnChGgEiLnrt8nQ@B3e@Yl9ISNMY6wEJKbzNpGS0m@KX0pCtXASdpBhglN/rwzRydlg4p4 "JavaScript (Node.js) ‚Äì 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]
# [Uiua](https://www.uiua.org/), 8 bytes
```
‚Ü•‚àß‚äÉ‚ãÖ+‚Ü•.0
```
[Try it online!](https://www.uiua.org/pad?src=ZiDihpAg4oal4oin4oqD4ouFK-KGpS4wCgpmIDFfMl8zXzQKZiAxXzJfM180XzUKZiAyXzJfMV8xXzJfMV8xXzIKZiAzXzFfNF8xXzVfOV8yCmYgOV84XzdfOV85Xzg=)
```
‚Ü•‚àß‚äÉ‚ãÖ+‚Ü•.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]
# [Vyxal](https://github.com/Vyxal/Vyxal) `G`, 59 [bitsv2](https://github.com/Vyxal/Vyncode/blob/main/README.md), 7.375 bytes
```
·∫è·πó'¬Ø‚Äπg;ƒ∞·π†
```
[Try it Online!](https://vyxal.pythonanywhere.com/?v=2#WyJHfj0iLCIiLCLhuo/huZcnwq/igLlnO8Sw4bmgIiwiIiwiWzEsMiwzLDRdICAgICAgICAgLT4gNlxuWzEsMiwzLDQsNV0gICAgICAgLT4gOVxuWzIsMiwxLDEsMiwxLDEsMl0gLT4gN1xuWzMsMSw0LDEsNSw5LDJdICAgLT4gMTZcbls5LDgsNyw5LDksOF0gICAgIC0+IDI2Il0=)
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](https://vyxal.github.io/Luminespire).
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 21 bytes
```
Ôº¶¬≤‚äûœÖ‚Å∞Ôº¶Ôº°‚âî‚ü¶‚Å∫Œπ¬ßœÖ¬π‚åàœÖ‚üßœÖÔº©‚åàœÖ
```
[Try it online!](https://tio.run/##RYu9CoMwFEb3PsUd74VbqLYdipM4ORSyhwzB/hiIsSS54ttH26XDt5xzvmG0cZitL@U1R8CaQEkaURhO1Bx@rA8fyUgEbUruHVArLwkdQ5v78Hiu37giYrjb1U0yoZBhkP2uogsZO5sy/h1RU4rWZ674su/KN66NKcfFbw "Charcoal ‚Äì 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]
# [Scala 3](https://www.scala-lang.org/), 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!](https://ato.pxeger.com/run?1=hc_BSsNAEAZgvPoQMscdnErTtNhGNuDBg1BPxVPpYbJNSspmK8lWlJAn8RIP-k76NE6b9hoPMz-z-zEwH9-VYcth-3txtUu2qfHwxLmD-hJgnWZQyKC43FQR3Jclvy8XvszdZoURPLvcgz5KgBd59dapgt8W-0LN88qrgEYU0hgR_yM06UMjQQEF595HQwFjqQnN-uGMpnQrSLJjjdQrW-hQBAe1fHR-pWPpcufX3meD6c-D1XEtUDElqO1NtrPreZp5pYY0RKwNV6k6fpJBHSs-bISE-Npgc3eamm7Z5ynbtss_)
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 39 bytes
```
a=>a.map(v=>q=(v+=p)>(p=q)?v:p,p=q=0)|q
```
[Try it online!](https://tio.run/##rY/NDoIwDIDvPsWOW6zgxp8zGT4IWciCYDQIQ8xOvjsWhWiCR7e0XfL1S9eLcaYvbmd73zTtsRwqNRiVGu9qLHUq7RR1a2VZSq3q2MHtLeBDbdmjG4q26du69Or2RCuacRAQQKjJdBgjvk9iQrIcSY5k9duASH8bEg2O/QFGtHAEOhz4nPXbSdAZZ4zeWDEvzABpiBGBRDpP4zHJxknhy5KQLzwJO0iQYNWfXwr05OwgWe725zttKvjwBA "JavaScript (Node.js) ‚Äì 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]
# 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](https://codegolf.stackexchange.com/a/265384/52210).  
Also runs in \$O(n)\$ complexity.
[Try it online.](https://tio.run/##rVHLasNADLznK0ROu3hj4jxoY@OU0nNzydH4oDqb4kfWYVd2Ccbf7spOQn@gLCuNBmkYoQJbXBSncsgqdA4@MTfdDCA3pO0ZMw2HsZwIyATHJAWUEXP9jIMjpDyDAxiIB1zsu7GP4qWy8TI613acgDJEaWNRejHJvaDYyrcypMhqaqwBG/VDNGpdm6@KtR6SbZ2f4MJ2xJFsbr6TFOXdyijbogXSjj7Q6dDoH5icJWnXBWql1mrTqydSW8YrxoEKnpGZNecN/63aTfVOvaoXxpyn2X9@fS8n8wDHmyN98euG/CsvRpURBR/Bbyiv/Hdr8eZ8qu9Li@eO0puHMPeMn/1Rjyv0wy8)
**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]
# [Python](https://www.python.org), 48 bytes
```
lambda a,b=0,c=0:max(b:=max(d+c,c:=b)for d in a)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=rdDdboIwFAfw7FKeopftPCrlQy1J9yKONAUkNkEgih97lt2YLNs7bU-zU2zjC0jT_iHn15OWz5_-Y9h17e2rlu_fp6GerX_DRu-LShMNhQyhlGG211daZNJGNS2hzGTB6u5AKmJaopnbJy4702wJz4KJAQUdvCpp2v40UDY_9o3BDCb9wbQDNVDT7Vk31DAGnWtw-3uZbjhEEEOSE__M3sgSY7EgG4U1hbXAK0jzhxJOcTQxzhRdhI4D92tu3co528tam7iijvE7wZmCsHbsypd3bTsmoxSg0ApYwwrfMXN_gshZ4R3W7FmfPMZbRPz-0_4B)
\$O(n)\$ complexity.
Loops over the list. On each prefix, `b` and `c` are the largest such sums of the two previous prefixes.
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 41 bytes
```
.+
$*
+`^((.+).*)¬∂\2(.*)¬∂
$1$3¬∂$1
O^`
\G1
```
[Try it online!](https://tio.run/##K0otycxL/K@qEZyg819Pm0tFi0s7IU5DQ09bU09L89C2GCMNMM2lYqhifGibiiGXf1wCV4y74f//hjpGOsY6JlxQWseUywjIMtQxhJFcxkDSBIhNdSyBPEsdCx1zIAtIAwA "Retina 0.8.2 ‚Äì 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]
# [Nibbles](http://golfscript.com/nibbles/index.html), 9.5 bytes (19 nibbles)
```
`//$`,1:`/@]+/@$$]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m708LzMpKSe1eMGCpaUlaboWmxL09VUSdAytEvQdYrX1HVRUYiESUPnN0UrRxjqGOiZAbKpjqWMUqxQLlQIA)
Runs in polynomial time.  
Direct port of [my R answer](https://codegolf.stackexchange.com/a/265383/95126), which is itself inspired by [G B's answer](https://codegolf.stackexchange.com/a/265384/95126).
```
  /                 # 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]
# [JavaScript (Node.js)](https://nodejs.org), 47 bytes
```
x=>x.map(e=(t,i)=>e=x[i]=(t+=~~x[i-2])<e?e:t)|e
```
[Try it online!](https://tio.run/##bc7fCoIwFAbw@55il46OyvyTLZo9iAwRW2GYSkp4Eb66fVZSYIOds/Htx9klu2dtfiuazq7qoxlPauxV3DvXrLGMsjoquIqN6pNC47ZWw4Cj7Wm@Nwez6/jDjHldtXVpnLI@WycrEeSRT4Fmn8U5c122YSxJkaRIVv8FhfpXSAiB9z52uDAejCAxV/02Ecw0Y3JTR11IH2mAHZJEOk8TG5ZMk4KXkpQunKQtRUjQ9feXHpycDZLxCQ "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# [Python](https://www.python.org), 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!](https://ato.pxeger.com/run?1=PYxJDoMwDEX3nCJLB1ypTGKQOEMPgLIIDRGRIEQodDhLN2zaO3GbppR2Yfu_J30_XuZuu1Evy3O28pCvmax6PjSCE44NntEXpSBcCyJh4DdwkiIPPp6OE9mUo4bu9eDaqb4loMpKaTNboLT0CDGT0hYk-O2F96BofWR0ryzrqa5DjDDGhDHvnzHdKHIUYvjbm4tdStykWOymwBwzR-4y9v37Bg)
Adapted from [G B's answer](https://codegolf.stackexchange.com/a/265384/113573). It only works if the array is at least three elements long.
[Answer]
# [C (clang)](http://clang.llvm.org/), \$\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!](https://tio.run/##rVLLTsMwELz7K0ZBBcdxUfpAQN20HxJysJKWWipu5Lhconx72DhQDrQ3FMn27Mx6J7sup@VR2/e@t9KrPRdaChe3@5PjwmU2S5XQituMgmu/pZBfpbHPbCJ0kqiuvzO2PJ6rHdaNr8zp8bBh7PNkKuZ3jefGegjtXMxaBgzISLidV4xgffblQTv@kD/EijDVBDfIkCpQTm4KhSQxMVEkdpS959GkmVSRhMEWtEVYIaJ9lI@3cAIS91Ql4J/EAtMNJtWbjYID4jrGiGIf2lg@WP41KQbzTV6QlzZUH34kL@IWM4m5xEJiKZGik7fZp2uCeRDM5LfycvirXARqGVa66vWGjOIvEs9BMJ6vufrv71IjpbWTEKIOEw0TrKlroX8KFEadJOMEw4MQ9dD4/gs "C (clang) ‚Äì Try It Online")
---
# [C (gcc)](https://gcc.gnu.org/), \$\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!](https://tio.run/##rZLPboMwDMbveYpPTFVDSCdoO60t/fMgjEMUShupowjoLohXH3NC113GrQLFNv7F/oijZyet@z7npmiE8luhdkIdcq6CyN@qZJ4GFN7tRiVRugnjrn8xhb7csiO2dZOZ6@t5z9jX1WSsOdaNLQWhqspnLQNsZGJGXnlr9FlVfJpM/Zji/FqBG@wQxiA8MWmMIDA@pQiuaGPOvUk9yTwJgwPIeNjAIzvgQxVuW1nvd0uK2R6T7KO4g6EFO8Yoyz6VKbiV@idOWNF1kpKQ1rW2P5CkfotIYi6xkFhKhPSik@PA2wgzd0wk7/DD@RdeuOzSrVRwPU5SaiXx7pjBH1H47CeUjy4hrZ2EEKWbr5tnScfoDjQGfUYZBMM83c0QpZ1E/63zizrV/Yxuz06v1j8 "C (gcc) ‚Äì Try It Online")
[Answer]
# [Erlang](https://www.erlang.org), 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!](https://ato.pxeger.com/run?1=hY_PCoJAEMbvPYV4iF36ttw00oLATh7q1k0khNwIUkMMAtMX6eKl3qljb9JIWUcH5g_z_WaGuT2i7Bgm-_rZF3G6Ox8jFoeHhA97Irqc0ixnvhpJaE1zJAM-vJ9zJeznWrEVFwuKKAwYJQ0o5gcoXCxLEuLwwqjk86btXTd_RbENilaGO_DK39JXc4VtuSYWPY3skM5UmsVhzvTqVCU6NJ-2SYxhwgp4wNGNYdIFjgmUkG3swk2CLPIJnG7YgY0pgZQb9PtoXX_yGw)
[Answer]
# [Elixir](https://elixir-lang.org), 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!](https://ato.pxeger.com/run?1=fZC9CsIwFIX3PMUdE7wW7Q_WQTcHB9FdHGqTQKBNRS0USp_EpYvuPo6rT2KSKi7VcEnOzfm44eRyE5mq1LG9cyHzgpeZgFWiNPDiWp7lMH5sjAGSZowXpE5w38wWusy9o-BlKmiG9QhHDUoNFTp7OK_zpKJGMkwGVSM0Z-RzQ0z3nvsEsJPz7jECZi3XntKng0jPVNLtGMFHCBDCHWN_fYSoH_EdMnb1Ff1s4MzQ7RHC9CdonBhh4hCrO8oEs-EIsb_n2VSUdUnbtjtf)
[Answer]
# [Racket](https://racket-lang.org/), 99 bytes
Golfed version. [Try it online!](https://tio.run/##dY7fCoJQDIfvfYofdNGkm/xHedWDiBdTj3FoHsUM6ultJ4kIdLCN7ftgG7m@mWneCbsrxmWgxrTWGVALCUnMBOn7gQqBlAXjWBaVlpBsC3IPkYvXOn6CUanv3boZ/5YHbVSzX37id6Nj68IAoMbeB@GXOH93TxFiJEjV3YbI1nGsOEL0retSoijVzJBvKTnOOCnW7p8OguXb@Q0)
```
(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!](https://tio.run/##hY/dCsIwDIXv9xQHvLDijftDd@WDDJFu66QYu7Ef0KevaeeY3sxAE3L6JZx0sryrwdoNSXND57sgEJWqtVEQD/m89uMD1A@7ABCkBlDTtBA5S06@IJc4cC44O4YpXUOYkeg8z03htkGi@FKmXWXVeXIhIPZcRSmnDx8/trTxfirdtyRfZBarWxEiQozEjfxBkK5BEUMhwjmvoTEDCb8U2TqY4YQjQ1w/N/lbrH0D)
```
#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]
# [Rust](https://www.rust-lang.org/), 90 bytes
Golfed version. [Try it online!](https://tio.run/##hc9LCoMwEAbgfU8RXU3oVHxi7cNjdFNKCTZCQGPRtFitZ7dTwXUCk3@GfAykfXVmLjWrhdLA2bhhdJ6t0qbSDrjj5CLr4C0L5xpgiBHGN86PdoWJxYXkAgzW26IjMjFVgpnVZrjHlBzlIqf//zoQh4ssTioKc77LKcZKGujxw8/CozXNXRnZAvfKpnoA@Ohz/C7vOFB6teiB@n470M51nOb5Bw)
```
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!](https://tio.run/##jdBfC4IwEADwdz/F6dNGV/iXapUfo5cIsTlBUIs5I1A/ux2abz04uO3gfsdt021jxjGvoUqLmnHoLKD10kVtytpmTjc4SLVP0rQVeytp3zz0McDwzvlprcVolfZJe@gt@6qegGRIEeFxZccRD7gnTefkB8uanj@TVGsBVyXPReDHHLYxUPL7lVIZYCnCg8MFCO5oyDMpjNKM7/JnmTHmIrgcoZ8ZguyBNSYTQlYvIWjIUkhhA3K57h9hDeP4BQ)
```
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]
# [OCaml](http://www.ocaml.org/), 104 bytes
Golfed version. [Try it online!](https://tio.run/##lY1NCsIwEIX3nuItE2yl1RZ/QnsCbyAS0jbVQJJKGzEL715jENwqDMObj/cxQyuMnmctHUbZwkBXRrj2Co2HcleczmmdPf3h4Ke0Di0ikoZWRzW5VT/ojmvZO9LfbeQ@rYkRHgJNIpaeUpIlGdVQFh8cHxGKagHcRmUdl7bTykqQyYX7woeeBwxicMoZ1gwbhuJMKfvPYCh/ldZRyuN8w6/2JtaLuEuG/R9q6O4YtlF657c3vwA)
```
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!](https://tio.run/##nY7NCoMwEITvPsUcDbXgL20N9kVERG2sgRhFI/TQd7dJ0PZsISy7s/vNZGiqXqyrYAoTa9BXr3JeeohZIXOAXe@YGNkEt/JQE2RoF9koPkh9AryRFzjfDYwK9aZ1aaqMuqPb1tPlhI5A6Tsuv2vfg09MruOYUJfY/HHiUpVMPgSXDO6s9Pwsh7bUsrW0v80DipAioogLQug/HEVyDA0tGtj3a455RBaKbU0obocNNHGluFjU9IZe1w8)
```
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]));
```
]