A Shelf With Matching Ends

Hard

Items stand in a row on a shelf, each with a value: an integer that may be negative. The values from left to right are given in items. You may take any items off the shelf (or none), and the rest keep their order. The display is finished if at least two items remain and the leftmost and rightmost ones have the same value. Return the largest total value of a finished display.

Example 1

items=[4, -2, 7, 4, 3, 7] → 21

Keep 7, 4, 3, 7: the ends match and the sum is 21. Using the 4s as ends gives only 4 + 7 + 4 = 15.

Example 2

items=[-5, 6, -1, -3, -1] → -2

The only equal pair is the two -1s. The -3 between them is dropped: -1 + -1 = -2.

Example 3

items=[2, 2] → 4

Constraints

2 ≤ len(items) ≤ 10⁵
-10⁴ ≤ items[i] ≤ 10⁴
At least one value appears in items twice

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Prefix Sum

Similar problems

Disjoint Segments With a Target Sum Medium Shift a Segment to Match Medium The Heaviest Reading Day Hard Four Equal Pieces Hard Narrowest Range Touching Every List Hard

Input

items=[4, -2, 7, 4, 3, 7]

Expected

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