Strongest Signal With One Mute
Preview mode. Log in to edit, run, submit, and save progress.
Strongest Signal With One Mute
A ground-station antenna logs $N$ consecutive signal-strength readings $A_1, A_2, \ldots, A_N$. Interference can push a reading negative, so the log is a mix of strong spikes and ugly dips. To assemble a highlight reel, the station picks a non-empty contiguous window of the log - some block $A_l, A_{l+1}, \ldots, A_r$ with $1 \le l \le r \le N$. Before the window is scored, an engineer may additionally mute at most one reading inside the chosen window, erasing it from the total. Muting is optional - a window may be scored exactly as recorded - but the window must still contain at least one reading after the mute, so a window of length one can never use it. The score of the window is the sum of the readings that remain. Over every choice of window and every legal use of the mute, report the strongest score the station can achieve. ### Function Description Complete the function `strongestSegment` provided in the editor. The function receives the following parameters:
| Parameter | Type | Description |
|---|---|---|
| $N$ | integer | the number of readings in the log |
| $A$ | array of integers | the signal strengths $A_1, \ldots, A_N$ (may be negative) |
The function must return a single integer: the maximum achievable window score. Note that the answer can be negative. ### Input Format - The first line contains a single integer $N$. - The second line contains $N$ space-separated integers $A_1, \ldots, A_N$. ### Output Format Return a single integer: the maximum sum of a non-empty contiguous window after muting at most one of its readings. ### Notes - The window must be contiguous before muting; the mute removes one reading from strictly inside the chosen block, and the remaining readings keep their positions. - Muting is optional - using zero mutes is always allowed. - You may never mute the only reading of a window: the window must be non-empty after the mute, so a length-$1$ window is always scored as-is. - If every reading is negative, the best answer is the single largest reading (muting cannot empty the window).
Examples
```text 5 3 -8 4 5 -2 ```
```text
Explanation: Choose the window $[3, -8, 4, 5]$ (readings $1$ through $4$) and mute the reading $-8$. The remaining sum is $3 + 4 + 5 = 12$. Without any mute the best window is $[4, 5]$ with sum $9$, so spending the mute to bridge the two positive runs is worth it. No other window/mute combination beats $12$.
Approach hint
Forget the mute for a moment. The best non-empty contiguous window with no mute is the classic Kadane's algorithm: the best window ending at index $i$ either extends the previous one or restarts at $A_i$.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.
```text
5
3 -8 4 5 -2
``````text