A Round Cake and Two Neighbors

Hard

A round cake is cut into pieces of different sizes, and the number of pieces is a multiple of three. The sizes, listed clockwise, are given in pieces. You share the cake with two friends: you pick any remaining piece, then one friend takes the nearest remaining piece counterclockwise from it and the other takes the nearest one clockwise. This repeats until the cake is gone. Return the largest total size you can collect for yourself.

Example 1

pieces=[2, 5, 3, 6, 1, 4] → 11

Take the 6; its neighbors 3 and 1 go to the friends. The circle [2, 5, 4] remains; take the 5 and the friends get 2 and 4. Total 6 + 5 = 11.

Example 2

pieces=[7, 9, 7, 3, 2, 2] → 14

Taking the 9 hands both 7s to the friends. It is better to take the two 7s one after another: 7 + 7 = 14.

Example 3

pieces=[4, 1, 8] → 8

Constraints

3 ≤ len(pieces) ≤ 500
len(pieces) is a multiple of 3
1 ≤ pieces[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Dynamic Programming Heap (Priority Queue)

Similar problems

Fuel Stops Along the Way Hard The Heaviest Reading Day Hard Growing Capital Project by Project Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard

Input

pieces=[2, 5, 3, 6, 1, 4]

Expected

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