HackerRank Problem: Max Score — Why do we not consider all permutations of a set?

Revision en1, by Lance_HAOH, 2017-06-11 19:51:41

Hi. I am having problem trying to upsolve the "Max Score" problem which was used in HackerRank's Rookie Rank 3.

Here is the link to the problem.

After reading the editorial, I am puzzled why the recurrence does not consider all permutations of elements in subset(S,i) because the order in which we choose the elements in the subset also affects the overall sum.

For easier reference, I have reproduced the puzzling part of the editorial here. Credits to HackerRank for the editorial.

I tried asking in the problem's forum but I have not received any reply for more than 3 weeks. Could someone please advise me why we do not need to consider all permutations of elements?

Thanks in advance.

Tags #hackerrank, #dp


  Rev. Lang. By When Δ Comment
en1 English Lance_HAOH 2017-06-11 19:51:41 927 Initial revision (published)