For simplicity you can calculate two different sets, one with all elements except the first and the other with all elements except the last one, cause the first and the last element can't be in the desired sequence. So now we have a linear sequence which we want to maximize the sum.
Suppose dp[i] is the maximum sum after checking the elements to position i.
dp[i] = max( element[i]+dp[i-2], element[i-1]+dp[i-3] )
What does it mean? The first (element[i]+dp[i-2]) means it's better to include element 'i' in the set and the second means it's better to include element 'i-1' in the set.
No comments:
Post a Comment