Stuck on certain DP problems.

[little joey]

You only have to go upto MAX*MAXCOST/2 and halve your runtime. Why? You have to consider the (extreme) case that you have to add up all first MAX/2 coins before you can subtract the remaining MAX/2 coins.

Then you can further halve your runtime by calculating TOTSUM and using TOTSUM/2, as I suggested in my prev. post. This addaption changed the runtime of your code to 0.23 sec.