Maximum summed powersets with non-adjacent items Announcing the arrival of Valued Associate...

Denied boarding although I have proper visa and documentation. To whom should I make a complaint?

Do wooden building fires get hotter than 600°C?

Is grep documentation wrong?

Old style "caution" boxes

What is the longest distance a player character can jump in one leap?

Can a party unilaterally change candidates in preparation for a General election?

How to compare two different files line by line in unix?

How do pianists reach extremely loud dynamics?

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

Why are the trig functions versine, haversine, exsecant, etc, rarely used in modern mathematics?

Is it cost-effective to upgrade an old-ish Giant Escape R3 commuter bike with entry-level branded parts (wheels, drivetrain)?

Is there such thing as an Availability Group failover trigger?

8 Prisoners wearing hats

Is there a kind of relay only consumes power when switching?

Can an alien society believe that their star system is the universe?

What is homebrew?

How to convince students of the implication truth values?

Do square wave exist?

Why aren't air breathing engines used as small first stages

Compare a given version number in the form major.minor.build.patch and see if one is less than the other

First console to have temporary backward compatibility

What's the meaning of "fortified infraction restraint"?

Is it a good idea to use CNN to classify 1D signal?

Is the Standard Deduction better than Itemized when both are the same amount?



Maximum summed powersets with non-adjacent items



Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
The PPCG Site design is on its way - help us make it awesome!
Sandbox for Proposed ChallengesGeneralised Array RiffleRemove leading and trailing zeroesMaximum Maxima!Find every digit from the largest columnFind the “Recursive Size” of a ListSwap indices and valuesGenerate all Sublist PartitionsCompare Two Lists by Their MaximumFind an array that fits a set of sumsNon-overlapping Matrix Sum












14












$begingroup$


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 powerset 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 of 9) at the 0-based indices [0,2,6].


  • [4,5,4,3] would result in either [4,4] (with a sum of 8) at the 0-based indices [0,2] or [5,3] (also with a sum of 8) at the 0-based indices [1,3].


  • [5,5,10,100,10,5] would result in [5,100,5] (with a sum of 110) 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 powerset 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 powersets
[[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.



  • You are allowed to output all possible powersets 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









share|improve this question











$endgroup$












  • $begingroup$
    If there is more than one identical set (but from different indices) is it ok to list all of them? e.g. [5,100,5] twice for your third example.
    $endgroup$
    – Nick Kennedy
    16 hours ago










  • $begingroup$
    powersetis 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.
    $endgroup$
    – Expired Data
    15 hours ago










  • $begingroup$
    @NickKennedy Yes, that's allowed, will edit the description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    @Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    Just to be sure: outputting the indices isn't an option, is it?
    $endgroup$
    – Shaggy
    7 hours ago
















14












$begingroup$


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 powerset 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 of 9) at the 0-based indices [0,2,6].


  • [4,5,4,3] would result in either [4,4] (with a sum of 8) at the 0-based indices [0,2] or [5,3] (also with a sum of 8) at the 0-based indices [1,3].


  • [5,5,10,100,10,5] would result in [5,100,5] (with a sum of 110) 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 powerset 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 powersets
[[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.



  • You are allowed to output all possible powersets 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









share|improve this question











$endgroup$












  • $begingroup$
    If there is more than one identical set (but from different indices) is it ok to list all of them? e.g. [5,100,5] twice for your third example.
    $endgroup$
    – Nick Kennedy
    16 hours ago










  • $begingroup$
    powersetis 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.
    $endgroup$
    – Expired Data
    15 hours ago










  • $begingroup$
    @NickKennedy Yes, that's allowed, will edit the description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    @Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    Just to be sure: outputting the indices isn't an option, is it?
    $endgroup$
    – Shaggy
    7 hours ago














14












14








14





$begingroup$


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 powerset 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 of 9) at the 0-based indices [0,2,6].


  • [4,5,4,3] would result in either [4,4] (with a sum of 8) at the 0-based indices [0,2] or [5,3] (also with a sum of 8) at the 0-based indices [1,3].


  • [5,5,10,100,10,5] would result in [5,100,5] (with a sum of 110) 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 powerset 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 powersets
[[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.



  • You are allowed to output all possible powersets 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









share|improve this question











$endgroup$




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 powerset 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 of 9) at the 0-based indices [0,2,6].


  • [4,5,4,3] would result in either [4,4] (with a sum of 8) at the 0-based indices [0,2] or [5,3] (also with a sum of 8) at the 0-based indices [1,3].


  • [5,5,10,100,10,5] would result in [5,100,5] (with a sum of 110) 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 powerset 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 powersets
[[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.



  • You are allowed to output all possible powersets 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






code-golf number array-manipulation integer






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 13 hours ago







Kevin Cruijssen

















asked 16 hours ago









Kevin CruijssenKevin Cruijssen

43.2k571221




43.2k571221












  • $begingroup$
    If there is more than one identical set (but from different indices) is it ok to list all of them? e.g. [5,100,5] twice for your third example.
    $endgroup$
    – Nick Kennedy
    16 hours ago










  • $begingroup$
    powersetis 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.
    $endgroup$
    – Expired Data
    15 hours ago










  • $begingroup$
    @NickKennedy Yes, that's allowed, will edit the description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    @Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    Just to be sure: outputting the indices isn't an option, is it?
    $endgroup$
    – Shaggy
    7 hours ago


















  • $begingroup$
    If there is more than one identical set (but from different indices) is it ok to list all of them? e.g. [5,100,5] twice for your third example.
    $endgroup$
    – Nick Kennedy
    16 hours ago










  • $begingroup$
    powersetis 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.
    $endgroup$
    – Expired Data
    15 hours ago










  • $begingroup$
    @NickKennedy Yes, that's allowed, will edit the description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    @Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago






  • 1




    $begingroup$
    Just to be sure: outputting the indices isn't an option, is it?
    $endgroup$
    – Shaggy
    7 hours ago
















$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g. [5,100,5] twice for your third example.
$endgroup$
– Nick Kennedy
16 hours ago




$begingroup$
If there is more than one identical set (but from different indices) is it ok to list all of them? e.g. [5,100,5] twice for your third example.
$endgroup$
– Nick Kennedy
16 hours ago












$begingroup$
powersetis 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.
$endgroup$
– Expired Data
15 hours ago




$begingroup$
powersetis 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.
$endgroup$
– Expired Data
15 hours ago












$begingroup$
@NickKennedy Yes, that's allowed, will edit the description.
$endgroup$
– Kevin Cruijssen
13 hours ago




$begingroup$
@NickKennedy Yes, that's allowed, will edit the description.
$endgroup$
– Kevin Cruijssen
13 hours ago




1




1




$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
13 hours ago




$begingroup$
@Arnauld Yes, if the values are key-value pairs with their index it's clear which indexed values are meant in the input, so they can be in any order. Will also edit this into the challenge description.
$endgroup$
– Kevin Cruijssen
13 hours ago




1




1




$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
7 hours ago




$begingroup$
Just to be sure: outputting the indices isn't an option, is it?
$endgroup$
– Shaggy
7 hours ago










11 Answers
11






active

oldest

votes


















4












$begingroup$


05AB1E, 14 bytes



Saved 1 byte thanks to Kevin Cruijssen



ā<æʒĆ¥≠W}èΣO}θ


Try it online!
or as a Test Suite



Explanation



ā<               # push [0 ... len(input)-1]
æ # compute powerset
ʒ } # filter, keep lists where:
≠W # no element is 1 in the
¥ # deltas
Ć # of the list with the head appended
è # index into the input with each
ΣO} # sort by sum
θ # take the last element





share|improve this answer











$endgroup$













  • $begingroup$
    You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
    $endgroup$
    – Kevin Cruijssen
    13 hours ago












  • $begingroup$
    @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
    $endgroup$
    – Emigna
    13 hours ago



















3












$begingroup$


Brachylog (v2), 14 bytes



{~ba~c∋₁ᵐ}ᶠ+ᵒt


Try it online!



Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.



{~ba~c∋₁ᵐ}ᶠ+ᵒt
~b Prepend an arbitrary element to the input
a Take a prefix or suffix of the resulting list
~c Ordered partition into contiguous sublists
∋₁ Take the second element
ᵐ of each sublist
{ }ᶠ Find all possible ways to do this
+ᵒ Sort by sum
t Take the greatest


The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.






share|improve this answer











$endgroup$





















    3












    $begingroup$

    JavaScript (ES6),  138 132 130 129  126 bytes



    Outputs key-value pairs.





    a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r


    Try it online!



    Step 1



    We first compute the powerset of the input with $[value, index]$ pairs.



    a.reduce((a, x, i) => // for each value x at position i:
    [ // update a[] to a new array consisting of:
    ...a, // all previous entries
    ...a.map(y => // for each value y in a[]:
    [[x, i], ...y] // append [x, i], followed by all original entries
    ) // end of map()
    ], // end of new array
    [[]] // start with a = [[]]
    ) // end of reduce()


    Step 2



    We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.



    .map(m =              // initialize m to a non-numeric value
    a => // for each entry a[] in the powerset:
    a.some(s = p = // initialize s and p to non numeric values
    ([v, i]) => // for each value v and each index i in a[]:
    p - ( // compute p - i
    s = ~~s + v, // add v to s
    p = i // update p to i
    ) < 2 // if p - i is less than 2, yield true
    ) | // end of some()
    s < m || // unless some() was truthy or s is less than m,
    (r = a, m = s) // save a[] in r[] and update m to s
    ) && r // end of map(); return r[]





    share|improve this answer











    $endgroup$





















      2












      $begingroup$


      Wolfram Language (Mathematica), 144 bytes



      If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],{2,x}]&@#,FreeQ[Differences@#,1]&]&@a)]),{Max@a},g[[#]]&@@@Position[m,d]]&


      Try it online!






      share|improve this answer









      $endgroup$





















        2












        $begingroup$

        Pyth, 19 bytes



        esDm@LQdtf!q#1.+TyU


        Try it online here, or verify all the test cases at once here.



        esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
        Trailing Q inferred
        UQ Generate range [0-len(Q))
        y Take the powerset of the above
        f Filter keep elements of the above, as T, using:
        .+T Take differences of consecutive elements of T
        q#1 Keep those differences equal to 1
        ! Logical NOT - empty lists evaluate to true, populated ones to false
        Result of the filter is those sets without consecutive numbers
        t Drop the first element (empty set)
        m Map the remaining sets, as d, using:
        L d For each element of d...
        @ Q ... get the element in Q with that index
        sD Order the sets by their sum
        e Take the last element, implicit print





        share|improve this answer











        $endgroup$





















          2












          $begingroup$


          Husk, 11 bytes



          ►Σ†!¹mü≈tṖŀ


          Try it online!



          Explanation



          ►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
          ŀ Indices: [1,2,3,4]
          Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
          t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
          m For each,
          ü de-duplicate by
          ≈ differing by at most 1.
          For example, [1,2,4] becomes [1,4].
          † Deep map
          !¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
          ► Maximum by
          Σ sum: [5,4]





          share|improve this answer











          $endgroup$





















            1












            $begingroup$


            Haskell, 300 168 bytes





            import Data.List
            h[]=1>2
            h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
            z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]


            Try it online!



            -132 bytes thanks to all the feedback from @nimi :)





            Original



            Ungolfed (original)



            import Data.List
            import Data.Function

            f :: [Int] -> [(Int, Int)] -- attach indices for later use
            f [] = []
            f xs = zip xs [0..length xs]

            g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
            g [] = []
            g (x:xs) = (map fst x, map snd x) : g xs

            h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
            h [] = False
            h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
            j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
            j xs = filter ((elements, indices) -> h indices) xs

            k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
            k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

            l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
            l xs = snd $ last $ sortBy (compare `on` fst) xs

            z -- put things together
            ```





            share|improve this answer










            New contributor




            bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.






            $endgroup$









            • 1




              $begingroup$
              Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
              $endgroup$
              – nimi
              13 hours ago












            • $begingroup$
              .... Try it online!.
              $endgroup$
              – nimi
              13 hours ago










            • $begingroup$
              oh, and no need to import Data.Function anymore.
              $endgroup$
              – nimi
              13 hours ago










            • $begingroup$
              That's great, thanks for the feedback :)
              $endgroup$
              – bugs
              13 hours ago










            • $begingroup$
              Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
              $endgroup$
              – nimi
              12 hours ago



















            1












            $begingroup$


            Jelly, 16 14 bytes



            JŒPḊf’$ÐḟịµSÞṪ


            Try it online!



            Thanks to @EriktheOutgolfer for saving 2 bytes!






            share|improve this answer











            $endgroup$













            • $begingroup$
              14 bytes.
              $endgroup$
              – Erik the Outgolfer
              11 hours ago



















            1












            $begingroup$


            Charcoal, 46 bytes



            ≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ


            Try it online! Link is to verbose version of code. Explanation:



            ≔⟦υ⟧η


            The variable u is predefined with an empty list. This is put in a list which is assigned to h. These variables act as accumulators. u contains the sublists that include the latest element of the input q while h contains the sublists that do not (and therefore are suitable for appending the next element of the input).



            Fθ«


            Loop over the elements of the input.



            ≔υζ


            Save the list of sublists that contain the previous element.



            ≔Eη⁺κ⟦ι⟧υ


            Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push here as I need to clone the list.)



            ≔⁺ζηη»


            Concatenate both previous sublists into the new list of sublists that do not contain the current element.



            ≔Φ⁺υηιη


            Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).



            ≔EηΣιζ


            Compute the sums of all of the sublists.



            I§η⌕ζ⌈ζ


            Find an index of the greatest sum and output the corresponding sublist.






            share|improve this answer









            $endgroup$





















              0












              $begingroup$


              Japt -h, 21 bytes



              Ever have one of those challenges where you completely forget how to golf?!



              ð¤à fÊk_än ø1îmgUÃñx


              Try it






              share|improve this answer









              $endgroup$





















                0












                $begingroup$

                T-SQL, 122 bytes



                Input is a table variable.



                This query picks all values from the table variable, join it with all values 2 or more positions later recusively and show the text generated for the highest sum of the values.



                WITH C as(SELECT i j,x y,x*1v
                FROM @ UNION ALL SELECT i,y+','+x,v+x
                FROM @ JOIN C ON j+1<i)SELECT
                TOP 1y FROM C ORDER BY-v


                Try it online ungolfed






                share|improve this answer











                $endgroup$














                  Your Answer






                  StackExchange.ifUsing("editor", function () {
                  StackExchange.using("externalEditor", function () {
                  StackExchange.using("snippets", function () {
                  StackExchange.snippets.init();
                  });
                  });
                  }, "code-snippets");

                  StackExchange.ready(function() {
                  var channelOptions = {
                  tags: "".split(" "),
                  id: "200"
                  };
                  initTagRenderer("".split(" "), "".split(" "), channelOptions);

                  StackExchange.using("externalEditor", function() {
                  // Have to fire editor after snippets, if snippets enabled
                  if (StackExchange.settings.snippets.snippetsEnabled) {
                  StackExchange.using("snippets", function() {
                  createEditor();
                  });
                  }
                  else {
                  createEditor();
                  }
                  });

                  function createEditor() {
                  StackExchange.prepareEditor({
                  heartbeatType: 'answer',
                  autoActivateHeartbeat: false,
                  convertImagesToLinks: false,
                  noModals: true,
                  showLowRepImageUploadWarning: true,
                  reputationToPostImages: null,
                  bindNavPrevention: true,
                  postfix: "",
                  imageUploader: {
                  brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
                  contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
                  allowUrls: true
                  },
                  onDemand: true,
                  discardSelector: ".discard-answer"
                  ,immediatelyShowMarkdownHelp:true
                  });


                  }
                  });














                  draft saved

                  draft discarded


















                  StackExchange.ready(
                  function () {
                  StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f183390%2fmaximum-summed-powersets-with-non-adjacent-items%23new-answer', 'question_page');
                  }
                  );

                  Post as a guest















                  Required, but never shown

























                  11 Answers
                  11






                  active

                  oldest

                  votes








                  11 Answers
                  11






                  active

                  oldest

                  votes









                  active

                  oldest

                  votes






                  active

                  oldest

                  votes









                  4












                  $begingroup$


                  05AB1E, 14 bytes



                  Saved 1 byte thanks to Kevin Cruijssen



                  ā<æʒĆ¥≠W}èΣO}θ


                  Try it online!
                  or as a Test Suite



                  Explanation



                  ā<               # push [0 ... len(input)-1]
                  æ # compute powerset
                  ʒ } # filter, keep lists where:
                  ≠W # no element is 1 in the
                  ¥ # deltas
                  Ć # of the list with the head appended
                  è # index into the input with each
                  ΣO} # sort by sum
                  θ # take the last element





                  share|improve this answer











                  $endgroup$













                  • $begingroup$
                    You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
                    $endgroup$
                    – Kevin Cruijssen
                    13 hours ago












                  • $begingroup$
                    @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
                    $endgroup$
                    – Emigna
                    13 hours ago
















                  4












                  $begingroup$


                  05AB1E, 14 bytes



                  Saved 1 byte thanks to Kevin Cruijssen



                  ā<æʒĆ¥≠W}èΣO}θ


                  Try it online!
                  or as a Test Suite



                  Explanation



                  ā<               # push [0 ... len(input)-1]
                  æ # compute powerset
                  ʒ } # filter, keep lists where:
                  ≠W # no element is 1 in the
                  ¥ # deltas
                  Ć # of the list with the head appended
                  è # index into the input with each
                  ΣO} # sort by sum
                  θ # take the last element





                  share|improve this answer











                  $endgroup$













                  • $begingroup$
                    You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
                    $endgroup$
                    – Kevin Cruijssen
                    13 hours ago












                  • $begingroup$
                    @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
                    $endgroup$
                    – Emigna
                    13 hours ago














                  4












                  4








                  4





                  $begingroup$


                  05AB1E, 14 bytes



                  Saved 1 byte thanks to Kevin Cruijssen



                  ā<æʒĆ¥≠W}èΣO}θ


                  Try it online!
                  or as a Test Suite



                  Explanation



                  ā<               # push [0 ... len(input)-1]
                  æ # compute powerset
                  ʒ } # filter, keep lists where:
                  ≠W # no element is 1 in the
                  ¥ # deltas
                  Ć # of the list with the head appended
                  è # index into the input with each
                  ΣO} # sort by sum
                  θ # take the last element





                  share|improve this answer











                  $endgroup$




                  05AB1E, 14 bytes



                  Saved 1 byte thanks to Kevin Cruijssen



                  ā<æʒĆ¥≠W}èΣO}θ


                  Try it online!
                  or as a Test Suite



                  Explanation



                  ā<               # push [0 ... len(input)-1]
                  æ # compute powerset
                  ʒ } # filter, keep lists where:
                  ≠W # no element is 1 in the
                  ¥ # deltas
                  Ć # of the list with the head appended
                  è # index into the input with each
                  ΣO} # sort by sum
                  θ # take the last element






                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited 13 hours ago

























                  answered 15 hours ago









                  EmignaEmigna

                  48.1k434146




                  48.1k434146












                  • $begingroup$
                    You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
                    $endgroup$
                    – Kevin Cruijssen
                    13 hours ago












                  • $begingroup$
                    @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
                    $endgroup$
                    – Emigna
                    13 hours ago


















                  • $begingroup$
                    You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
                    $endgroup$
                    – Kevin Cruijssen
                    13 hours ago












                  • $begingroup$
                    @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
                    $endgroup$
                    – Emigna
                    13 hours ago
















                  $begingroup$
                  You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
                  $endgroup$
                  – Kevin Cruijssen
                  13 hours ago






                  $begingroup$
                  You may not be happy, but it's still 4 bytes shorter than my initial solution. ;) And you can golf 1 more changing ¤ª to Ć.
                  $endgroup$
                  – Kevin Cruijssen
                  13 hours ago














                  $begingroup$
                  @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
                  $endgroup$
                  – Emigna
                  13 hours ago




                  $begingroup$
                  @KevinCruijssen: Oh yeah! For some reason I had convinced myself I needed a repeat element at the end. Thanks!
                  $endgroup$
                  – Emigna
                  13 hours ago











                  3












                  $begingroup$


                  Brachylog (v2), 14 bytes



                  {~ba~c∋₁ᵐ}ᶠ+ᵒt


                  Try it online!



                  Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.



                  {~ba~c∋₁ᵐ}ᶠ+ᵒt
                  ~b Prepend an arbitrary element to the input
                  a Take a prefix or suffix of the resulting list
                  ~c Ordered partition into contiguous sublists
                  ∋₁ Take the second element
                  ᵐ of each sublist
                  { }ᶠ Find all possible ways to do this
                  +ᵒ Sort by sum
                  t Take the greatest


                  The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.






                  share|improve this answer











                  $endgroup$


















                    3












                    $begingroup$


                    Brachylog (v2), 14 bytes



                    {~ba~c∋₁ᵐ}ᶠ+ᵒt


                    Try it online!



                    Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.



                    {~ba~c∋₁ᵐ}ᶠ+ᵒt
                    ~b Prepend an arbitrary element to the input
                    a Take a prefix or suffix of the resulting list
                    ~c Ordered partition into contiguous sublists
                    ∋₁ Take the second element
                    ᵐ of each sublist
                    { }ᶠ Find all possible ways to do this
                    +ᵒ Sort by sum
                    t Take the greatest


                    The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.






                    share|improve this answer











                    $endgroup$
















                      3












                      3








                      3





                      $begingroup$


                      Brachylog (v2), 14 bytes



                      {~ba~c∋₁ᵐ}ᶠ+ᵒt


                      Try it online!



                      Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.



                      {~ba~c∋₁ᵐ}ᶠ+ᵒt
                      ~b Prepend an arbitrary element to the input
                      a Take a prefix or suffix of the resulting list
                      ~c Ordered partition into contiguous sublists
                      ∋₁ Take the second element
                      ᵐ of each sublist
                      { }ᶠ Find all possible ways to do this
                      +ᵒ Sort by sum
                      t Take the greatest


                      The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.






                      share|improve this answer











                      $endgroup$




                      Brachylog (v2), 14 bytes



                      {~ba~c∋₁ᵐ}ᶠ+ᵒt


                      Try it online!



                      Function submission; input from the left, output from the right, as usual. Very slow; a five-element list is probably the maximum for testing on TIO.



                      {~ba~c∋₁ᵐ}ᶠ+ᵒt
                      ~b Prepend an arbitrary element to the input
                      a Take a prefix or suffix of the resulting list
                      ~c Ordered partition into contiguous sublists
                      ∋₁ Take the second element
                      ᵐ of each sublist
                      { }ᶠ Find all possible ways to do this
                      +ᵒ Sort by sum
                      t Take the greatest


                      The results we get from prefixes aren't incorrect, but also aren't interesting; all possible results are generated via taking a suffix (which is possibly the list itself, but cannot be empty), but "suffix" is more verbose in Brachylog than "prefix or suffix", so I went with the version that's terser (and less efficient but still correct). The basic idea is that for each element we want in the output list, the partition into contiguous sublists needs to place that element and the element before into the same sublist (because the element is the second element of the sublist), so two consecutive elements can't appear in the result. On the other hand, it's fairly clear that any list without two consecutive elements can appear in the result. So once we have all possible candidate lists, we can just take the sums of all of them and see which one is largest.







                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      answered 12 hours ago


























                      community wiki





                      ais523
























                          3












                          $begingroup$

                          JavaScript (ES6),  138 132 130 129  126 bytes



                          Outputs key-value pairs.





                          a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r


                          Try it online!



                          Step 1



                          We first compute the powerset of the input with $[value, index]$ pairs.



                          a.reduce((a, x, i) => // for each value x at position i:
                          [ // update a[] to a new array consisting of:
                          ...a, // all previous entries
                          ...a.map(y => // for each value y in a[]:
                          [[x, i], ...y] // append [x, i], followed by all original entries
                          ) // end of map()
                          ], // end of new array
                          [[]] // start with a = [[]]
                          ) // end of reduce()


                          Step 2



                          We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.



                          .map(m =              // initialize m to a non-numeric value
                          a => // for each entry a[] in the powerset:
                          a.some(s = p = // initialize s and p to non numeric values
                          ([v, i]) => // for each value v and each index i in a[]:
                          p - ( // compute p - i
                          s = ~~s + v, // add v to s
                          p = i // update p to i
                          ) < 2 // if p - i is less than 2, yield true
                          ) | // end of some()
                          s < m || // unless some() was truthy or s is less than m,
                          (r = a, m = s) // save a[] in r[] and update m to s
                          ) && r // end of map(); return r[]





                          share|improve this answer











                          $endgroup$


















                            3












                            $begingroup$

                            JavaScript (ES6),  138 132 130 129  126 bytes



                            Outputs key-value pairs.





                            a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r


                            Try it online!



                            Step 1



                            We first compute the powerset of the input with $[value, index]$ pairs.



                            a.reduce((a, x, i) => // for each value x at position i:
                            [ // update a[] to a new array consisting of:
                            ...a, // all previous entries
                            ...a.map(y => // for each value y in a[]:
                            [[x, i], ...y] // append [x, i], followed by all original entries
                            ) // end of map()
                            ], // end of new array
                            [[]] // start with a = [[]]
                            ) // end of reduce()


                            Step 2



                            We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.



                            .map(m =              // initialize m to a non-numeric value
                            a => // for each entry a[] in the powerset:
                            a.some(s = p = // initialize s and p to non numeric values
                            ([v, i]) => // for each value v and each index i in a[]:
                            p - ( // compute p - i
                            s = ~~s + v, // add v to s
                            p = i // update p to i
                            ) < 2 // if p - i is less than 2, yield true
                            ) | // end of some()
                            s < m || // unless some() was truthy or s is less than m,
                            (r = a, m = s) // save a[] in r[] and update m to s
                            ) && r // end of map(); return r[]





                            share|improve this answer











                            $endgroup$
















                              3












                              3








                              3





                              $begingroup$

                              JavaScript (ES6),  138 132 130 129  126 bytes



                              Outputs key-value pairs.





                              a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r


                              Try it online!



                              Step 1



                              We first compute the powerset of the input with $[value, index]$ pairs.



                              a.reduce((a, x, i) => // for each value x at position i:
                              [ // update a[] to a new array consisting of:
                              ...a, // all previous entries
                              ...a.map(y => // for each value y in a[]:
                              [[x, i], ...y] // append [x, i], followed by all original entries
                              ) // end of map()
                              ], // end of new array
                              [[]] // start with a = [[]]
                              ) // end of reduce()


                              Step 2



                              We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.



                              .map(m =              // initialize m to a non-numeric value
                              a => // for each entry a[] in the powerset:
                              a.some(s = p = // initialize s and p to non numeric values
                              ([v, i]) => // for each value v and each index i in a[]:
                              p - ( // compute p - i
                              s = ~~s + v, // add v to s
                              p = i // update p to i
                              ) < 2 // if p - i is less than 2, yield true
                              ) | // end of some()
                              s < m || // unless some() was truthy or s is less than m,
                              (r = a, m = s) // save a[] in r[] and update m to s
                              ) && r // end of map(); return r[]





                              share|improve this answer











                              $endgroup$



                              JavaScript (ES6),  138 132 130 129  126 bytes



                              Outputs key-value pairs.





                              a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r


                              Try it online!



                              Step 1



                              We first compute the powerset of the input with $[value, index]$ pairs.



                              a.reduce((a, x, i) => // for each value x at position i:
                              [ // update a[] to a new array consisting of:
                              ...a, // all previous entries
                              ...a.map(y => // for each value y in a[]:
                              [[x, i], ...y] // append [x, i], followed by all original entries
                              ) // end of map()
                              ], // end of new array
                              [[]] // start with a = [[]]
                              ) // end of reduce()


                              Step 2



                              We then look for the maximum sum $m$ among these sets, discarding sets with at least two adjacent elements. The best set is stored in $r$.



                              .map(m =              // initialize m to a non-numeric value
                              a => // for each entry a[] in the powerset:
                              a.some(s = p = // initialize s and p to non numeric values
                              ([v, i]) => // for each value v and each index i in a[]:
                              p - ( // compute p - i
                              s = ~~s + v, // add v to s
                              p = i // update p to i
                              ) < 2 // if p - i is less than 2, yield true
                              ) | // end of some()
                              s < m || // unless some() was truthy or s is less than m,
                              (r = a, m = s) // save a[] in r[] and update m to s
                              ) && r // end of map(); return r[]






                              share|improve this answer














                              share|improve this answer



                              share|improve this answer








                              edited 3 hours ago

























                              answered 15 hours ago









                              ArnauldArnauld

                              81.5k797336




                              81.5k797336























                                  2












                                  $begingroup$


                                  Wolfram Language (Mathematica), 144 bytes



                                  If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],{2,x}]&@#,FreeQ[Differences@#,1]&]&@a)]),{Max@a},g[[#]]&@@@Position[m,d]]&


                                  Try it online!






                                  share|improve this answer









                                  $endgroup$


















                                    2












                                    $begingroup$


                                    Wolfram Language (Mathematica), 144 bytes



                                    If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],{2,x}]&@#,FreeQ[Differences@#,1]&]&@a)]),{Max@a},g[[#]]&@@@Position[m,d]]&


                                    Try it online!






                                    share|improve this answer









                                    $endgroup$
















                                      2












                                      2








                                      2





                                      $begingroup$


                                      Wolfram Language (Mathematica), 144 bytes



                                      If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],{2,x}]&@#,FreeQ[Differences@#,1]&]&@a)]),{Max@a},g[[#]]&@@@Position[m,d]]&


                                      Try it online!






                                      share|improve this answer









                                      $endgroup$




                                      Wolfram Language (Mathematica), 144 bytes



                                      If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],{2,x}]&@#,FreeQ[Differences@#,1]&]&@a)]),{Max@a},g[[#]]&@@@Position[m,d]]&


                                      Try it online!







                                      share|improve this answer












                                      share|improve this answer



                                      share|improve this answer










                                      answered 15 hours ago









                                      J42161217J42161217

                                      14.2k21353




                                      14.2k21353























                                          2












                                          $begingroup$

                                          Pyth, 19 bytes



                                          esDm@LQdtf!q#1.+TyU


                                          Try it online here, or verify all the test cases at once here.



                                          esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
                                          Trailing Q inferred
                                          UQ Generate range [0-len(Q))
                                          y Take the powerset of the above
                                          f Filter keep elements of the above, as T, using:
                                          .+T Take differences of consecutive elements of T
                                          q#1 Keep those differences equal to 1
                                          ! Logical NOT - empty lists evaluate to true, populated ones to false
                                          Result of the filter is those sets without consecutive numbers
                                          t Drop the first element (empty set)
                                          m Map the remaining sets, as d, using:
                                          L d For each element of d...
                                          @ Q ... get the element in Q with that index
                                          sD Order the sets by their sum
                                          e Take the last element, implicit print





                                          share|improve this answer











                                          $endgroup$


















                                            2












                                            $begingroup$

                                            Pyth, 19 bytes



                                            esDm@LQdtf!q#1.+TyU


                                            Try it online here, or verify all the test cases at once here.



                                            esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
                                            Trailing Q inferred
                                            UQ Generate range [0-len(Q))
                                            y Take the powerset of the above
                                            f Filter keep elements of the above, as T, using:
                                            .+T Take differences of consecutive elements of T
                                            q#1 Keep those differences equal to 1
                                            ! Logical NOT - empty lists evaluate to true, populated ones to false
                                            Result of the filter is those sets without consecutive numbers
                                            t Drop the first element (empty set)
                                            m Map the remaining sets, as d, using:
                                            L d For each element of d...
                                            @ Q ... get the element in Q with that index
                                            sD Order the sets by their sum
                                            e Take the last element, implicit print





                                            share|improve this answer











                                            $endgroup$
















                                              2












                                              2








                                              2





                                              $begingroup$

                                              Pyth, 19 bytes



                                              esDm@LQdtf!q#1.+TyU


                                              Try it online here, or verify all the test cases at once here.



                                              esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
                                              Trailing Q inferred
                                              UQ Generate range [0-len(Q))
                                              y Take the powerset of the above
                                              f Filter keep elements of the above, as T, using:
                                              .+T Take differences of consecutive elements of T
                                              q#1 Keep those differences equal to 1
                                              ! Logical NOT - empty lists evaluate to true, populated ones to false
                                              Result of the filter is those sets without consecutive numbers
                                              t Drop the first element (empty set)
                                              m Map the remaining sets, as d, using:
                                              L d For each element of d...
                                              @ Q ... get the element in Q with that index
                                              sD Order the sets by their sum
                                              e Take the last element, implicit print





                                              share|improve this answer











                                              $endgroup$



                                              Pyth, 19 bytes



                                              esDm@LQdtf!q#1.+TyU


                                              Try it online here, or verify all the test cases at once here.



                                              esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
                                              Trailing Q inferred
                                              UQ Generate range [0-len(Q))
                                              y Take the powerset of the above
                                              f Filter keep elements of the above, as T, using:
                                              .+T Take differences of consecutive elements of T
                                              q#1 Keep those differences equal to 1
                                              ! Logical NOT - empty lists evaluate to true, populated ones to false
                                              Result of the filter is those sets without consecutive numbers
                                              t Drop the first element (empty set)
                                              m Map the remaining sets, as d, using:
                                              L d For each element of d...
                                              @ Q ... get the element in Q with that index
                                              sD Order the sets by their sum
                                              e Take the last element, implicit print






                                              share|improve this answer














                                              share|improve this answer



                                              share|improve this answer








                                              edited 15 hours ago

























                                              answered 16 hours ago









                                              SokSok

                                              4,237925




                                              4,237925























                                                  2












                                                  $begingroup$


                                                  Husk, 11 bytes



                                                  ►Σ†!¹mü≈tṖŀ


                                                  Try it online!



                                                  Explanation



                                                  ►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
                                                  ŀ Indices: [1,2,3,4]
                                                  Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
                                                  t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
                                                  m For each,
                                                  ü de-duplicate by
                                                  ≈ differing by at most 1.
                                                  For example, [1,2,4] becomes [1,4].
                                                  † Deep map
                                                  !¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
                                                  ► Maximum by
                                                  Σ sum: [5,4]





                                                  share|improve this answer











                                                  $endgroup$


















                                                    2












                                                    $begingroup$


                                                    Husk, 11 bytes



                                                    ►Σ†!¹mü≈tṖŀ


                                                    Try it online!



                                                    Explanation



                                                    ►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
                                                    ŀ Indices: [1,2,3,4]
                                                    Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
                                                    t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
                                                    m For each,
                                                    ü de-duplicate by
                                                    ≈ differing by at most 1.
                                                    For example, [1,2,4] becomes [1,4].
                                                    † Deep map
                                                    !¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
                                                    ► Maximum by
                                                    Σ sum: [5,4]





                                                    share|improve this answer











                                                    $endgroup$
















                                                      2












                                                      2








                                                      2





                                                      $begingroup$


                                                      Husk, 11 bytes



                                                      ►Σ†!¹mü≈tṖŀ


                                                      Try it online!



                                                      Explanation



                                                      ►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
                                                      ŀ Indices: [1,2,3,4]
                                                      Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
                                                      t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
                                                      m For each,
                                                      ü de-duplicate by
                                                      ≈ differing by at most 1.
                                                      For example, [1,2,4] becomes [1,4].
                                                      † Deep map
                                                      !¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
                                                      ► Maximum by
                                                      Σ sum: [5,4]





                                                      share|improve this answer











                                                      $endgroup$




                                                      Husk, 11 bytes



                                                      ►Σ†!¹mü≈tṖŀ


                                                      Try it online!



                                                      Explanation



                                                      ►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
                                                      ŀ Indices: [1,2,3,4]
                                                      Ṗ Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
                                                      t Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
                                                      m For each,
                                                      ü de-duplicate by
                                                      ≈ differing by at most 1.
                                                      For example, [1,2,4] becomes [1,4].
                                                      † Deep map
                                                      !¹ indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
                                                      ► Maximum by
                                                      Σ sum: [5,4]






                                                      share|improve this answer














                                                      share|improve this answer



                                                      share|improve this answer








                                                      edited 12 hours ago

























                                                      answered 12 hours ago









                                                      ZgarbZgarb

                                                      26.8k462231




                                                      26.8k462231























                                                          1












                                                          $begingroup$


                                                          Haskell, 300 168 bytes





                                                          import Data.List
                                                          h[]=1>2
                                                          h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
                                                          z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]


                                                          Try it online!



                                                          -132 bytes thanks to all the feedback from @nimi :)





                                                          Original



                                                          Ungolfed (original)



                                                          import Data.List
                                                          import Data.Function

                                                          f :: [Int] -> [(Int, Int)] -- attach indices for later use
                                                          f [] = []
                                                          f xs = zip xs [0..length xs]

                                                          g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
                                                          g [] = []
                                                          g (x:xs) = (map fst x, map snd x) : g xs

                                                          h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
                                                          h [] = False
                                                          h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
                                                          j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
                                                          j xs = filter ((elements, indices) -> h indices) xs

                                                          k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
                                                          k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

                                                          l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
                                                          l xs = snd $ last $ sortBy (compare `on` fst) xs

                                                          z -- put things together
                                                          ```





                                                          share|improve this answer










                                                          New contributor




                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.






                                                          $endgroup$









                                                          • 1




                                                            $begingroup$
                                                            Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago












                                                          • $begingroup$
                                                            .... Try it online!.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            oh, and no need to import Data.Function anymore.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            That's great, thanks for the feedback :)
                                                            $endgroup$
                                                            – bugs
                                                            13 hours ago










                                                          • $begingroup$
                                                            Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
                                                            $endgroup$
                                                            – nimi
                                                            12 hours ago
















                                                          1












                                                          $begingroup$


                                                          Haskell, 300 168 bytes





                                                          import Data.List
                                                          h[]=1>2
                                                          h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
                                                          z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]


                                                          Try it online!



                                                          -132 bytes thanks to all the feedback from @nimi :)





                                                          Original



                                                          Ungolfed (original)



                                                          import Data.List
                                                          import Data.Function

                                                          f :: [Int] -> [(Int, Int)] -- attach indices for later use
                                                          f [] = []
                                                          f xs = zip xs [0..length xs]

                                                          g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
                                                          g [] = []
                                                          g (x:xs) = (map fst x, map snd x) : g xs

                                                          h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
                                                          h [] = False
                                                          h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
                                                          j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
                                                          j xs = filter ((elements, indices) -> h indices) xs

                                                          k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
                                                          k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

                                                          l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
                                                          l xs = snd $ last $ sortBy (compare `on` fst) xs

                                                          z -- put things together
                                                          ```





                                                          share|improve this answer










                                                          New contributor




                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.






                                                          $endgroup$









                                                          • 1




                                                            $begingroup$
                                                            Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago












                                                          • $begingroup$
                                                            .... Try it online!.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            oh, and no need to import Data.Function anymore.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            That's great, thanks for the feedback :)
                                                            $endgroup$
                                                            – bugs
                                                            13 hours ago










                                                          • $begingroup$
                                                            Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
                                                            $endgroup$
                                                            – nimi
                                                            12 hours ago














                                                          1












                                                          1








                                                          1





                                                          $begingroup$


                                                          Haskell, 300 168 bytes





                                                          import Data.List
                                                          h[]=1>2
                                                          h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
                                                          z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]


                                                          Try it online!



                                                          -132 bytes thanks to all the feedback from @nimi :)





                                                          Original



                                                          Ungolfed (original)



                                                          import Data.List
                                                          import Data.Function

                                                          f :: [Int] -> [(Int, Int)] -- attach indices for later use
                                                          f [] = []
                                                          f xs = zip xs [0..length xs]

                                                          g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
                                                          g [] = []
                                                          g (x:xs) = (map fst x, map snd x) : g xs

                                                          h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
                                                          h [] = False
                                                          h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
                                                          j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
                                                          j xs = filter ((elements, indices) -> h indices) xs

                                                          k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
                                                          k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

                                                          l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
                                                          l xs = snd $ last $ sortBy (compare `on` fst) xs

                                                          z -- put things together
                                                          ```





                                                          share|improve this answer










                                                          New contributor




                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.






                                                          $endgroup$




                                                          Haskell, 300 168 bytes





                                                          import Data.List
                                                          h[]=1>2
                                                          h(x:y)=fst$foldl(a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
                                                          z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]


                                                          Try it online!



                                                          -132 bytes thanks to all the feedback from @nimi :)





                                                          Original



                                                          Ungolfed (original)



                                                          import Data.List
                                                          import Data.Function

                                                          f :: [Int] -> [(Int, Int)] -- attach indices for later use
                                                          f [] = []
                                                          f xs = zip xs [0..length xs]

                                                          g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
                                                          g [] = []
                                                          g (x:xs) = (map fst x, map snd x) : g xs

                                                          h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
                                                          h [] = False
                                                          h (x:xs) = fst $ foldl (acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
                                                          j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
                                                          j xs = filter ((elements, indices) -> h indices) xs

                                                          k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
                                                          k xs = map ((elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

                                                          l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
                                                          l xs = snd $ last $ sortBy (compare `on` fst) xs

                                                          z -- put things together
                                                          ```






                                                          share|improve this answer










                                                          New contributor




                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.









                                                          share|improve this answer



                                                          share|improve this answer








                                                          edited 13 hours ago





















                                                          New contributor




                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.









                                                          answered 14 hours ago









                                                          bugsbugs

                                                          2014




                                                          2014




                                                          New contributor




                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.





                                                          New contributor





                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.






                                                          bugs is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                                          Check out our Code of Conduct.








                                                          • 1




                                                            $begingroup$
                                                            Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago












                                                          • $begingroup$
                                                            .... Try it online!.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            oh, and no need to import Data.Function anymore.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            That's great, thanks for the feedback :)
                                                            $endgroup$
                                                            – bugs
                                                            13 hours ago










                                                          • $begingroup$
                                                            Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
                                                            $endgroup$
                                                            – nimi
                                                            12 hours ago














                                                          • 1




                                                            $begingroup$
                                                            Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago












                                                          • $begingroup$
                                                            .... Try it online!.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            oh, and no need to import Data.Function anymore.
                                                            $endgroup$
                                                            – nimi
                                                            13 hours ago










                                                          • $begingroup$
                                                            That's great, thanks for the feedback :)
                                                            $endgroup$
                                                            – bugs
                                                            13 hours ago










                                                          • $begingroup$
                                                            Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
                                                            $endgroup$
                                                            – nimi
                                                            12 hours ago








                                                          1




                                                          1




                                                          $begingroup$
                                                          Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
                                                          $endgroup$
                                                          – nimi
                                                          13 hours ago






                                                          $begingroup$
                                                          Some tips: flip the element and its index within the pairs returned by f: f x=zip[0..length x]x, so f becomes f=zip[0..]. g is just g=map unzip. The function to filter with in j is h.fst (<- flipped pairs!). j=filter(h.fst). The foldl1+ from k is sum and with a pointfree pair making k=map((,)=<<sum.snd). sortBy(...) can be replaced by sortOn fst: l=snd.last.sortOn fst. Finally as you are using all functions only once, you can inline them into a single pointfree expression: z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
                                                          $endgroup$
                                                          – nimi
                                                          13 hours ago














                                                          $begingroup$
                                                          .... Try it online!.
                                                          $endgroup$
                                                          – nimi
                                                          13 hours ago




                                                          $begingroup$
                                                          .... Try it online!.
                                                          $endgroup$
                                                          – nimi
                                                          13 hours ago












                                                          $begingroup$
                                                          oh, and no need to import Data.Function anymore.
                                                          $endgroup$
                                                          – nimi
                                                          13 hours ago




                                                          $begingroup$
                                                          oh, and no need to import Data.Function anymore.
                                                          $endgroup$
                                                          – nimi
                                                          13 hours ago












                                                          $begingroup$
                                                          That's great, thanks for the feedback :)
                                                          $endgroup$
                                                          – bugs
                                                          13 hours ago




                                                          $begingroup$
                                                          That's great, thanks for the feedback :)
                                                          $endgroup$
                                                          – bugs
                                                          13 hours ago












                                                          $begingroup$
                                                          Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
                                                          $endgroup$
                                                          – nimi
                                                          12 hours ago




                                                          $begingroup$
                                                          Next h: we're looking for non-adjacent elements, i.e. the difference of adjacent indices must be >1. zipWith(-)=<<tail builds such a list of differences, but fails for the empty list, so we need an additional tail on the subsequences to get rid of it. Inline again. Try it online!
                                                          $endgroup$
                                                          – nimi
                                                          12 hours ago











                                                          1












                                                          $begingroup$


                                                          Jelly, 16 14 bytes



                                                          JŒPḊf’$ÐḟịµSÞṪ


                                                          Try it online!



                                                          Thanks to @EriktheOutgolfer for saving 2 bytes!






                                                          share|improve this answer











                                                          $endgroup$













                                                          • $begingroup$
                                                            14 bytes.
                                                            $endgroup$
                                                            – Erik the Outgolfer
                                                            11 hours ago
















                                                          1












                                                          $begingroup$


                                                          Jelly, 16 14 bytes



                                                          JŒPḊf’$ÐḟịµSÞṪ


                                                          Try it online!



                                                          Thanks to @EriktheOutgolfer for saving 2 bytes!






                                                          share|improve this answer











                                                          $endgroup$













                                                          • $begingroup$
                                                            14 bytes.
                                                            $endgroup$
                                                            – Erik the Outgolfer
                                                            11 hours ago














                                                          1












                                                          1








                                                          1





                                                          $begingroup$


                                                          Jelly, 16 14 bytes



                                                          JŒPḊf’$ÐḟịµSÞṪ


                                                          Try it online!



                                                          Thanks to @EriktheOutgolfer for saving 2 bytes!






                                                          share|improve this answer











                                                          $endgroup$




                                                          Jelly, 16 14 bytes



                                                          JŒPḊf’$ÐḟịµSÞṪ


                                                          Try it online!



                                                          Thanks to @EriktheOutgolfer for saving 2 bytes!







                                                          share|improve this answer














                                                          share|improve this answer



                                                          share|improve this answer








                                                          edited 11 hours ago

























                                                          answered 16 hours ago









                                                          Nick KennedyNick Kennedy

                                                          1,73649




                                                          1,73649












                                                          • $begingroup$
                                                            14 bytes.
                                                            $endgroup$
                                                            – Erik the Outgolfer
                                                            11 hours ago


















                                                          • $begingroup$
                                                            14 bytes.
                                                            $endgroup$
                                                            – Erik the Outgolfer
                                                            11 hours ago
















                                                          $begingroup$
                                                          14 bytes.
                                                          $endgroup$
                                                          – Erik the Outgolfer
                                                          11 hours ago




                                                          $begingroup$
                                                          14 bytes.
                                                          $endgroup$
                                                          – Erik the Outgolfer
                                                          11 hours ago











                                                          1












                                                          $begingroup$


                                                          Charcoal, 46 bytes



                                                          ≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ


                                                          Try it online! Link is to verbose version of code. Explanation:



                                                          ≔⟦υ⟧η


                                                          The variable u is predefined with an empty list. This is put in a list which is assigned to h. These variables act as accumulators. u contains the sublists that include the latest element of the input q while h contains the sublists that do not (and therefore are suitable for appending the next element of the input).



                                                          Fθ«


                                                          Loop over the elements of the input.



                                                          ≔υζ


                                                          Save the list of sublists that contain the previous element.



                                                          ≔Eη⁺κ⟦ι⟧υ


                                                          Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push here as I need to clone the list.)



                                                          ≔⁺ζηη»


                                                          Concatenate both previous sublists into the new list of sublists that do not contain the current element.



                                                          ≔Φ⁺υηιη


                                                          Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).



                                                          ≔EηΣιζ


                                                          Compute the sums of all of the sublists.



                                                          I§η⌕ζ⌈ζ


                                                          Find an index of the greatest sum and output the corresponding sublist.






                                                          share|improve this answer









                                                          $endgroup$


















                                                            1












                                                            $begingroup$


                                                            Charcoal, 46 bytes



                                                            ≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ


                                                            Try it online! Link is to verbose version of code. Explanation:



                                                            ≔⟦υ⟧η


                                                            The variable u is predefined with an empty list. This is put in a list which is assigned to h. These variables act as accumulators. u contains the sublists that include the latest element of the input q while h contains the sublists that do not (and therefore are suitable for appending the next element of the input).



                                                            Fθ«


                                                            Loop over the elements of the input.



                                                            ≔υζ


                                                            Save the list of sublists that contain the previous element.



                                                            ≔Eη⁺κ⟦ι⟧υ


                                                            Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push here as I need to clone the list.)



                                                            ≔⁺ζηη»


                                                            Concatenate both previous sublists into the new list of sublists that do not contain the current element.



                                                            ≔Φ⁺υηιη


                                                            Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).



                                                            ≔EηΣιζ


                                                            Compute the sums of all of the sublists.



                                                            I§η⌕ζ⌈ζ


                                                            Find an index of the greatest sum and output the corresponding sublist.






                                                            share|improve this answer









                                                            $endgroup$
















                                                              1












                                                              1








                                                              1





                                                              $begingroup$


                                                              Charcoal, 46 bytes



                                                              ≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ


                                                              Try it online! Link is to verbose version of code. Explanation:



                                                              ≔⟦υ⟧η


                                                              The variable u is predefined with an empty list. This is put in a list which is assigned to h. These variables act as accumulators. u contains the sublists that include the latest element of the input q while h contains the sublists that do not (and therefore are suitable for appending the next element of the input).



                                                              Fθ«


                                                              Loop over the elements of the input.



                                                              ≔υζ


                                                              Save the list of sublists that contain the previous element.



                                                              ≔Eη⁺κ⟦ι⟧υ


                                                              Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push here as I need to clone the list.)



                                                              ≔⁺ζηη»


                                                              Concatenate both previous sublists into the new list of sublists that do not contain the current element.



                                                              ≔Φ⁺υηιη


                                                              Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).



                                                              ≔EηΣιζ


                                                              Compute the sums of all of the sublists.



                                                              I§η⌕ζ⌈ζ


                                                              Find an index of the greatest sum and output the corresponding sublist.






                                                              share|improve this answer









                                                              $endgroup$




                                                              Charcoal, 46 bytes



                                                              ≔⟦υ⟧ηFθ«≔υζ≔Eη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔EηΣιζI§η⌕ζ⌈ζ


                                                              Try it online! Link is to verbose version of code. Explanation:



                                                              ≔⟦υ⟧η


                                                              The variable u is predefined with an empty list. This is put in a list which is assigned to h. These variables act as accumulators. u contains the sublists that include the latest element of the input q while h contains the sublists that do not (and therefore are suitable for appending the next element of the input).



                                                              Fθ«


                                                              Loop over the elements of the input.



                                                              ≔υζ


                                                              Save the list of sublists that contain the previous element.



                                                              ≔Eη⁺κ⟦ι⟧υ


                                                              Take all of the sublists that do not contain the previous element, append the current element, and save the result as the list of sublists that contain the current element. (I don't use Push here as I need to clone the list.)



                                                              ≔⁺ζηη»


                                                              Concatenate both previous sublists into the new list of sublists that do not contain the current element.



                                                              ≔Φ⁺υηιη


                                                              Concatenate the sublists one last time and remove the original empty list (which Charcoal can't sum anyway).



                                                              ≔EηΣιζ


                                                              Compute the sums of all of the sublists.



                                                              I§η⌕ζ⌈ζ


                                                              Find an index of the greatest sum and output the corresponding sublist.







                                                              share|improve this answer












                                                              share|improve this answer



                                                              share|improve this answer










                                                              answered 10 hours ago









                                                              NeilNeil

                                                              83k745179




                                                              83k745179























                                                                  0












                                                                  $begingroup$


                                                                  Japt -h, 21 bytes



                                                                  Ever have one of those challenges where you completely forget how to golf?!



                                                                  ð¤à fÊk_än ø1îmgUÃñx


                                                                  Try it






                                                                  share|improve this answer









                                                                  $endgroup$


















                                                                    0












                                                                    $begingroup$


                                                                    Japt -h, 21 bytes



                                                                    Ever have one of those challenges where you completely forget how to golf?!



                                                                    ð¤à fÊk_än ø1îmgUÃñx


                                                                    Try it






                                                                    share|improve this answer









                                                                    $endgroup$
















                                                                      0












                                                                      0








                                                                      0





                                                                      $begingroup$


                                                                      Japt -h, 21 bytes



                                                                      Ever have one of those challenges where you completely forget how to golf?!



                                                                      ð¤à fÊk_än ø1îmgUÃñx


                                                                      Try it






                                                                      share|improve this answer









                                                                      $endgroup$




                                                                      Japt -h, 21 bytes



                                                                      Ever have one of those challenges where you completely forget how to golf?!



                                                                      ð¤à fÊk_än ø1îmgUÃñx


                                                                      Try it







                                                                      share|improve this answer












                                                                      share|improve this answer



                                                                      share|improve this answer










                                                                      answered 8 hours ago









                                                                      ShaggyShaggy

                                                                      19k21768




                                                                      19k21768























                                                                          0












                                                                          $begingroup$

                                                                          T-SQL, 122 bytes



                                                                          Input is a table variable.



                                                                          This query picks all values from the table variable, join it with all values 2 or more positions later recusively and show the text generated for the highest sum of the values.



                                                                          WITH C as(SELECT i j,x y,x*1v
                                                                          FROM @ UNION ALL SELECT i,y+','+x,v+x
                                                                          FROM @ JOIN C ON j+1<i)SELECT
                                                                          TOP 1y FROM C ORDER BY-v


                                                                          Try it online ungolfed






                                                                          share|improve this answer











                                                                          $endgroup$


















                                                                            0












                                                                            $begingroup$

                                                                            T-SQL, 122 bytes



                                                                            Input is a table variable.



                                                                            This query picks all values from the table variable, join it with all values 2 or more positions later recusively and show the text generated for the highest sum of the values.



                                                                            WITH C as(SELECT i j,x y,x*1v
                                                                            FROM @ UNION ALL SELECT i,y+','+x,v+x
                                                                            FROM @ JOIN C ON j+1<i)SELECT
                                                                            TOP 1y FROM C ORDER BY-v


                                                                            Try it online ungolfed






                                                                            share|improve this answer











                                                                            $endgroup$
















                                                                              0












                                                                              0








                                                                              0





                                                                              $begingroup$

                                                                              T-SQL, 122 bytes



                                                                              Input is a table variable.



                                                                              This query picks all values from the table variable, join it with all values 2 or more positions later recusively and show the text generated for the highest sum of the values.



                                                                              WITH C as(SELECT i j,x y,x*1v
                                                                              FROM @ UNION ALL SELECT i,y+','+x,v+x
                                                                              FROM @ JOIN C ON j+1<i)SELECT
                                                                              TOP 1y FROM C ORDER BY-v


                                                                              Try it online ungolfed






                                                                              share|improve this answer











                                                                              $endgroup$



                                                                              T-SQL, 122 bytes



                                                                              Input is a table variable.



                                                                              This query picks all values from the table variable, join it with all values 2 or more positions later recusively and show the text generated for the highest sum of the values.



                                                                              WITH C as(SELECT i j,x y,x*1v
                                                                              FROM @ UNION ALL SELECT i,y+','+x,v+x
                                                                              FROM @ JOIN C ON j+1<i)SELECT
                                                                              TOP 1y FROM C ORDER BY-v


                                                                              Try it online ungolfed







                                                                              share|improve this answer














                                                                              share|improve this answer



                                                                              share|improve this answer








                                                                              edited 1 hour ago

























                                                                              answered 2 hours ago









                                                                              t-clausen.dkt-clausen.dk

                                                                              2,104414




                                                                              2,104414






























                                                                                  draft saved

                                                                                  draft discarded




















































                                                                                  If this is an answer to a challenge…




                                                                                  • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.


                                                                                  • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
                                                                                    Explanations of your answer make it more interesting to read and are very much encouraged.


                                                                                  • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.



                                                                                  More generally…




                                                                                  • …Please make sure to answer the question and provide sufficient detail.


                                                                                  • …Avoid asking for help, clarification or responding to other answers (use comments instead).





                                                                                  draft saved


                                                                                  draft discarded














                                                                                  StackExchange.ready(
                                                                                  function () {
                                                                                  StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f183390%2fmaximum-summed-powersets-with-non-adjacent-items%23new-answer', 'question_page');
                                                                                  }
                                                                                  );

                                                                                  Post as a guest















                                                                                  Required, but never shown





















































                                                                                  Required, but never shown














                                                                                  Required, but never shown












                                                                                  Required, but never shown







                                                                                  Required, but never shown

































                                                                                  Required, but never shown














                                                                                  Required, but never shown












                                                                                  Required, but never shown







                                                                                  Required, but never shown







                                                                                  Popular posts from this blog

                                                                                  Why not use the yoke to control yaw, as well as pitch and roll? Announcing the arrival of...

                                                                                  Couldn't open a raw socket. Error: Permission denied (13) (nmap)Is it possible to run networking commands...

                                                                                  VNC viewer RFB protocol error: bad desktop size 0x0I Cannot Type the Key 'd' (lowercase) in VNC Viewer...