Hackerrank: Max Array Sum Solution

Approach

A subset can be one element only

Base cases:

• max at 0 is
  max(arr[0], 0)
• max at 1 is
  max(arr[0], arr[1], 0)

Then cases:

• max at
  i
  is
  max(arr[i], maxAt[i - 1], maxAt[i - 2] + arr[i], 0)

Tail 0 on every max because negative value is rejected

Implementation

1function maxSubsetSum(arr) {
2  const N = arr.length
3  const maxes = Array(N).fill(0)
4
5  maxes[0] = Math.max(arr[0], 0)
6  maxes[1] = Math.max(arr[0], arr[1], 0)
7  for (let i = 2; i < N; i++) {
8    maxes[i] = Math.max(arr[i], maxes[i - 1], maxes[i - 2] + arr[i], 0)
9  }
10
11  return maxes[N - 1]
12}