Take Only From the Ends

Medium

Jars of jam stand in a row on a shelf; jar i is worth values[i]. In one move you take one jar, either the leftmost or the rightmost of those still on the shelf. You must make exactly count moves. Return the largest total value of the jars you take.

Example 1

values=[3, 9, 1, 1, 2, 8], count=3 → 20

Take the two leftmost jars (3 and 9) and the rightmost one (8): 20. Three from either end alone gives only 13 or 11.

Example 2

values=[5, 1, 5], count=1 → 5

A single jar must come from an end, and both ends are worth 5.

Example 3

values=[2, 7, 4], count=3 → 13

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁴
1 ≤ count ≤ len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Prefix Sum Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Windows With a Small Product Medium Windows With an Exact Alarm Count Medium Longest Run of Ones With k Fixes Medium Stretches With k Odd Numbers Medium

Input

values=[3, 9, 1, 1, 2, 8], count=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.