Loading...
Loading...
Loading...
At a college fest stall, n cards lie face up in a row. Each card shows points, and some cards show negative points.
You take exactly k turns. In each turn you take one card from the left end or the right end of the row. Print the largest total of points you can collect.
Example 1
Input
7 3 1 2 3 4 5 6 1
Output
12
The best choice is the last three cards: 5 + 6 + 1 = 12.
Example 2
Input
5 2 5 1 1 100 1
Output
101
Taking the bigger end first gives 5 + 1 = 6. Taking two from the right gives 101.
Try the problem first. Open one hint at a time.
Choosing one end greedily each turn can fail: a small card may hide a large one behind it.
Whatever you do, you end with some i cards from the left and k − i cards from the right, for some i from 0 to k.
Start with all k cards from the left. Then, one by one, give back the innermost left card and take the next card from the right.
Keep the running total in a long and start best from the first total, not from 0, because all totals may be negative.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor