values of length n and an **odd** integer k. Choose exactly k non-empty, non-overlapping stretches of consecutive elements piece₁, piece₂, …, pieceₖ, ordered left to right: each one starts after the previous one ends. They do not have to cover the whole array.
The strength of the choice is
k · sum(piece₁) − (k − 1) · sum(piece₂) + (k − 2) · sum(piece₃) − … − 2 · sum(pieceₖ₋₁) + 1 · sum(pieceₖ)
so piece number j carries weight k − j + 1 and the signs alternate, starting with plus. Return the largest strength you can achieve.values=[3, -2, 4], k=3 → 17
The weights are 3, −2, 1. Each piece is a single element: 3 · 3 − 2 · (−2) + 1 · 4 = 17.
values=[2, 5, -1, 3], k=1 → 9
A single piece with weight 1: take the whole array, 2 + 5 − 1 + 3 = 9.
values=[1, -4, 2, 2, -3], k=3 → 15
Pieces [1], [−4] and [2, 2]: 3 · 1 − 2 · (−4) + 1 · 4 = 15. The final −3 is left out.
k is oddvalues=[3, -2, 4], k=3
17
Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.