Kadane, Minus One — Solution & Editorial

Back to the Problem

Two running Kadane states: best subarray ending here with no deletion, and with exactly one deletion (= extend the no-deletion state by skipping the current element, or extend the one-deletion state normally).

Complexity: O(N)

Watch out: The subarray must stay non-empty even after a deletion — track both states carefully.