BL
U

48. Maximum Subarray Sum with At Most One Deletion

Med.

Problem Description

Given an array of NN integers, find the maximum sum of a non-empty contiguous subarray after deleting at most one element (or zero elements).

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the maximum sum obtainable.

Example 1:
Input:
4
1 -2 0 3
Output:
4
Explanation: Deleting -2 gives subarray [1, 0, 3] with sum 4.
Example 2:
Input:
4
1 -2 -2 3
Output:
3
Explanation: Subarray [3] has sum 3.
Example 3:
Input:
3
-1 -1 -1
Output:
-1
Explanation: Cannot delete all elements; maximum single element is -1.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online