Best Sum After Banning a Value

Hard

You are given an integer array readings. At most once you may pick a value x and delete **every** occurrence of it, as long as the array does not become empty. After that (or with no deletion), look at the non-empty stretches of consecutive elements. Return the largest possible sum of such a stretch.

Example 1

readings=[4, -1, 3, -5, 6, -1, 2] → 13

Remove every -5: [4, -1, 3, 6, -1, 2] remains, and its best stretch is the whole array with sum 13.

Example 2

readings=[-7, -2, -7] → -2

Removing every -7 leaves [-2]; no stretch beats a sum of -2.

Example 3

readings=[5] → 5

The only value cannot be removed, since the array would become empty. The answer is 5.

Constraints

1 ≤ len(readings) ≤ 10⁵
-10⁶ ≤ readings[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Segment Tree Array Dynamic Programming

Similar problems

Ferry Runs From the Depot Hard Rising Chain With Small Steps Hard Squared Variety Total Hard Steep Subsequence With the Largest Sum Hard AND Pieces With Cheap Tails Hard

Input

readings=[4, -1, 3, -5, 6, -1, 2]

Expected

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