Max Sum of a Contiguous Segment After Removing at Most One Element
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Overview: A coding problem that asks for the largest sum of a non-empty contiguous segment of an integer array when at most one element of the segment may be removed. It tests linear-time reasoning about segment sums, the all-negative case, and the rule that at least one element must remain.
Read the full Oracle Software Engineer interview experience this question came from
Constraints
- 1 <= len(arr) <= 10^5
- -10^4 <= arr[k] <= 10^4 for every index k; values may be negative, zero or repeated.
- Every achievable value lies within [-10^9, 10^9], inside the signed 32-bit range.
Examples
Input: ([6],)
Expected Output: 6
Explanation: Source example 3: a one-element segment cannot have its only element removed.
Input: ([-10000],)
Expected Output: -10000
Explanation: Negative singleton at the lower value bound; no removal is allowed, so the answer is the element itself.
Hints
- Without any removal this is the best sum of a non-empty contiguous segment; the single optional removal adds one extra decision per segment.
- Removing an element only raises a segment's value when that element is negative, and only one element may go, so a segment holding two negatives keeps at least one of them.
- At least one element must remain, so when every element is negative the answer is negative, never 0.