Introduction:
Inspired by these two SO questions (no doubt from the same class): print the elements in the subarray of maximum sum without adjacent elements java and Maximum sum of non adjacent elements of an array, to be printed.
Challenge:
Given a list of integers, output a subsequence consisting of non-adjacent elements that have the highest sum. Here some examples:
[1,2,3,-1,-3,2,5]
would result in[1,3,5]
(with a sum of9
) at the 0-based indices[0,2,6]
.[4,5,4,3]
would result in either[4,4]
(with a sum of8
) at the 0-based indices[0,2]
or[5,3]
(also with a sum of8
) at the 0-based indices[1,3]
.[5,5,10,100,10,5]
would result in[5,100,5]
(with a sum of110
) at either the 0-based indices[0,3,5]
or[1,3,5]
.
What's most important about these examples above, the indices containing the elements are at least 2 apart from each other. If we look at the example [5,5,10,100,10,5]
more in depth: we have the following potential subsequence containing non-adjacent items; with their indices below it; with their sums below that:
[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]] // non-adjacent subsequences
[[5],[ 4],[ 3],[ 2],[1],[0],[ 3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1, 3],[0,5],[0, 4],[0, 3],[0, 2],[1, 3,5],[0, 3,5],[0, 2,5],[0, 2, 4]] // at these 0-based indices
[ 5, 10, 100, 10, 5, 5, 105, 15, 20, 10, 15, 105, 10, 15, 105, 15, 110, 110, 20, 25] // with these sums
^ ^ // and these two maximums
Since the maximum sums are 110
, we output [5,100,5]
as result.
Challenge rules:
- You are allowed to output key-value pairs of the index + value. So instead of
[5,100,5]
you can output[[0,5],[3,100],[5,5]]
or[[1,5],[3,100],[5,5]]
as result (or[[1,5],[4,100],[6,5]]
/[[2,5],[4,100],[6,5]]
when 1-based indexing is used instead of 0-based).- If you use key-value pairs, they can also be in reverse or random order, since it's clear which values are meant due to the paired index.
- Outputting just the indices without values isn't allowed. It should either output the values, or the values/indices as key-value pairs (or two separated lists for 'keys' and 'values' of the same size if key-value pairs are not possible in your language of choice).
- You are allowed to output all possible subsequences with the maximum sum instead of just one.
- As you can see from the examples, the input-list can contain negative and duplicated values as well. You can assume the input-integers are within the range [−999,999].
- The output-list cannot be empty and must always contain at least one element (if a list would only contain negative values, a list containing the single lowest negative value would then be output as result - see last two test cases).
- If there is one possible output but for multiple different indices, it's allowed to output both of them even though they might look duplicates. (i.e. the example above, may output
[[5,100,5],[5,100,5]]
for both possible index-combinations).
Test cases:
Input: Possible outputs: At 0-based indices: With sum:
[1,2,3,-1,-3,2,5] [1,3,5] [0,2,6] 9
[4,5,4,3] [4,4]/[5,3] [0,2]/[1,3] 8
[5,5,10,100,10,5] [5,100,5] [0,3,5]/[1,3,5] 110
[10] [10] [0] 10
[1,1,1] [1,1] [0,2] 2
[-3,7,4,-2,4] [7,4] [1,4] 11
[1,7,4,-2] [7] [1] 7
[1,2,-3,-4,5,6,-7] [2,6] [1,5] 8
[800,-31,0,0,421,726] [800,726]/[800,0,726] [0,5]/[0,3,5]/[0,2,5] 1526
[-1,7,8,-5,40,40] [8,40] [2,4]/[2,5] 48
[-5,-18,-3,-1,-10] [-1] [3] -1
[0,-3,-41,0,-99,-2,0] [0]/[0,0]/[0,0,0] [0]/[3]/[6]/[0,3]/
[0,6],[3,6]/[0,3,6] 0
powerset
is a set of subsets isn't it? but it looks like you are returning a set of subsequences? [4,5,4,3] would result in either [4,4] where [4,4] is clearly not a set.[1, 2, 3, 4, 5]
. The individual sublists aren't all power sets. "Power set" is not a correct term to describe what this challenge is asking for.