Quick 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.

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

Given an array of integers, choose a non-empty contiguous segment of it and, if you like, remove one element from that segment, as long as at least one element remains. Return the largest possible sum of the elements that remain. The report identifies this round's problem only by its number in a well-known practice set; the rules below state it completely. ### Function Signature ```python def max_segment_sum_with_one_removal(arr: list[int]) -> int: ``` ### Rules - A choice is a segment `arr[i..j]` with `0 <= i <= j < len(arr)`, together with either no removal or the removal of exactly one element `arr[m]` with `i <= m <= j`. - A removal is allowed only when the segment has at least two elements, so at least one element always remains. - The value of a choice is the sum of the segment's elements that were not removed. - Return the maximum value over all valid choices as a single integer. Only the value is returned, so the answer is unique even when several choices reach it. ### 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 **Example 1** ```text Input: arr = [2, -5, 3, -1, 4] Output: 8 ``` Take the whole array and remove `-5`: `2 + 3 + (-1) + 4 = 8`. A value of 9 would need both `-5` and `-1` removed, and only one removal is allowed. **Example 2** ```text Input: arr = [-3, -7, -2] Output: -2 ``` Every element is negative. The segment `[-2]` alone gives `-2`, as does `[-7, -2]` with `-7` removed. The answer cannot be 0, because at least one element must remain. **Example 3** ```text Input: arr = [6] Output: 6 ``` A one-element segment cannot have its only element removed.

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

Given an integer array `arr`, choose a non-empty contiguous segment `arr[i..j]` with `0 <= i <= j < len(arr)`. For that segment you may either keep every element or remove exactly one element `arr[m]` with `i <= m <= j`. A removal is allowed only when the segment has at least two elements, so at least one element always remains. The value of a choice is the sum of the segment's elements that were not removed. Implement `max_segment_sum_with_one_removal(arr)`, which returns the maximum value over all valid choices as a single integer. Only the value is returned, so the answer is unique even when several choices reach it. **Example 1** ```text Input: arr = [2, -5, 3, -1, 4] Output: 8 ``` Take the whole array and remove `-5`: `2 + 3 + (-1) + 4 = 8`. A value of 9 would need both `-5` and `-1` removed, and only one removal is allowed. **Example 2** ```text Input: arr = [-3, -7, -2] Output: -2 ``` Every element is negative. The segment `[-2]` alone gives `-2`, as does `[-7, -2]` with `-7` removed. The answer cannot be 0, because at least one element must remain. **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, so no value exceeds 2^31 - 1 and a 32-bit `int` holds the answer in Java and C++.

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

  1. Without any removal this is the best sum of a non-empty contiguous segment; the single optional removal adds one extra decision per segment.
  2. 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.
  3. At least one element must remain, so when every element is negative the answer is negative, never 0.

Best Segment Sum With At Most One Removal

hardOracleSoftware Engineer

Given an integer array arr, choose a non-empty contiguous segment arr[i..j] with 0 <= i <= j < len(arr). For that segment you may either keep every element or remove exactly one element arr[m] with i <= m <= j. A removal is allowed only when the segment has at least two elements, so at least one element always remains. The value of a choice is the sum of the segment's elements that were not removed.

Implement max_segment_sum_with_one_removal(arr), which returns the maximum value over all valid choices as a single integer. Only the value is returned, so the answer is unique even when several choices reach it.

Example 1

Input:  arr = [2, -5, 3, -1, 4]
Output: 8

Take the whole array and remove -5: 2 + 3 + (-1) + 4 = 8. A value of 9 would need both -5 and -1 removed, and only one removal is allowed.

Example 2

Input:  arr = [-3, -7, -2]
Output: -2

Every element is negative. The segment [-2] alone gives -2, as does [-7, -2] with -7 removed. The answer cannot be 0, because at least one element must remain.

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, so no value exceeds 2^31 - 1 and a 32-bit int holds the answer in Java and C++.

Examples

Example 1
Input
([6],)
Output
6
Notes
Source example 3: a one-element segment cannot have its only element removed.
Example 2
Input
([-10000],)
Output
-10000
Notes
Negative singleton at the lower value bound; no removal is allowed, so the answer is the element itself.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def max_segment_sum_with_one_removal(arr: list[int]) -> int:
Sample call
max_segment_sum_with_one_removal([6])
Language
Case 1
Input
([6],)
Expected
6
Case 2
Input
([-10000],)
Expected
-10000

Browse More Questions

Show the approach

Approach

Scan left to right and keep two running values for segments that end at the current index i. keep is the best sum of a segment ending at i with no removal; drop is the best value of a segment ending at i with exactly one element removed and at least one element left. For the next element a, drop becomes max(drop + a, keep): either a joins a segment that has already used its removal, or a itself is the removed element and the remainder is the best no-removal segment ending just before it, which is non-empty. keep becomes max(keep + a, a), the usual best-segment recurrence. The answer is the maximum of keep and drop over all indices.

Invariant: after index i is processed, keep and drop are exactly the best values among valid choices whose segment ends at i, without and with a removal. Every valid choice has a last index, so the running maximum over all indices covers every choice. A choice that removes the first element of its segment leaves a shorter segment with no removal, which keep already covers, so the two recurrences miss nothing.

Edge cases: drop starts at negative infinity (a large negative sentinel in Python, Java and C++) because a one-element segment cannot have a removal; this keeps the answer from becoming 0 when every element is negative, and a single-element array returns that element. Every intermediate value is an achievable value, so it stays inside [-10^9, 10^9]; Java and C++ still accumulate in 64-bit for safety and return a 32-bit int.

Time complexity:
O(n)
Space complexity:
O(1)