# 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}function maxSubsetSum(arr) {2  const N = arr.length3  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}```

## Tags

hackerrank

dynamic programming

## Next Post

Codility: TieRopes

Jan 30, 2021

Lesson 16 Greedy Algorithms

Search Posts