Codility: MaximumDoubleSliceSum Solution

Approach

Kadane algorithm

(X, Y, Z): X + 1, Z - 1, and skip Y

Maintain 2 kadane prefix, one for ending at (normal), one for starting at (reversed)

Implementation

1function solution(A) {
2  const N = A.length
3  const maxEndingAt = Array(N).fill(0)
4  const maxStartingAt = Array(N).fill(0)
5
6  for (let i = 1; i < N - 1; i++) {
7    maxEndingAt[i] = Math.max(0, maxEndingAt[i - 1] + A[i])
8  }
9  for (let i = N - 2; i > 0; i--) {
10    maxStartingAt[i] = Math.max(0, A[i] + maxStartingAt[i + 1])
11  }
12
13  let max = -Infinity
14  for (let i = 1; i < N - 1; i++) {
15    max = Math.max(max, maxEndingAt[i - 1] + maxStartingAt[i + 1])
16  }
17  return max
18}