[DAY25]Max Array Sum

Max Array Sum | HackerRank

Solution: Dynamic Programming. This question is not well defined, an single element also counts for a subset. Hence we need to divide this problem into several small problems and solve them respectively. Since we need to use DP, we need to set up our base cases first. The maximum subset sum at index 0, would be the input array element at index 0. Second, the maximum subset sum at index 1, would be the larger value of input array element at index 0 and input array element at index 1. From that forward, the maximum subset sum of the position would be either the value at the position of the input array, or the max value found so far(position minus one), or the max value from 2 positions back plus the current value.