LeetCode Problem 1191

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

LeetCode 1186 - Maximum Subarray Sum with One Deletion

Problem Understanding

This problem asks us to find the maximum possible sum of a contiguous subarray when we are allowed to delete at most one element from that chosen subarray.

The important detail is that the resulting subarray must still contain at least one element after deletion. That means we cannot delete every element and return 0 unless the array itself contains a valid non-empty subarray with sum 0.

The input is an integer array arr, which may contain positive numbers, negative numbers, or zeros. We need to return the largest achievable subarray sum after optionally removing one element.

A standard maximum subarray problem, solved with Kadane’s algorithm, only considers contiguous segments without deletion. This problem extends that idea by allowing one removal, which changes the state transitions significantly.

The constraints are important:

• The array length can be as large as 10^5
• Each element can range from -10^4 to 10^4

These constraints immediately rule out expensive approaches such as checking every subarray explicitly. Any solution worse than roughly O(n) or O(n log n) is likely too slow.

Several edge cases are especially important:

• Arrays containing all negative numbers
• Arrays where deletion is not beneficial
• Arrays where deleting a large negative number creates the optimal result
• Single-element arrays
• Arrays containing zeros

For example, if the input is [-1, -1, -1], the answer is -1, not 0, because deleting the only selected element would leave an empty subarray, which is not allowed.

Approaches

Brute Force Approach

A brute-force solution would examine every possible subarray. For each subarray, we could either:

• Keep all elements
• Delete exactly one element from that subarray

Then we would compute the resulting sums and track the maximum.

Suppose the array has length n. There are O(n^2) subarrays. For each subarray, trying every possible deletion costs another O(n). Computing sums naively adds additional overhead.

This produces an overall complexity near O(n^3), or O(n^2) with prefix sum optimization. Even O(n^2) is far too slow for n = 10^5.

The brute-force method is correct because it explicitly checks every valid possibility, but it is computationally impractical.

Optimal Dynamic Programming Approach

The key insight is that at every index, we only need to know two things:

• The maximum subarray sum ending at the current index without any deletion
• The maximum subarray sum ending at the current index with exactly one deletion already used

This creates a natural dynamic programming formulation.

Let:

• no_delete represent the best subarray ending at the current position with no deletion
• one_delete represent the best subarray ending at the current position after one deletion

For every new element:

• We either extend the previous subarray
• Or start a new subarray
• Or delete the current element

This allows us to process the array in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(1)	Checks all subarrays and deletions
Optimal Dynamic Programming	O(n)	O(1)	Tracks best states with and without deletion

Algorithm Walkthrough

1. Initialize two dynamic programming states.

no_delete stores the maximum subarray sum ending at the current index without deleting anything.

one_delete stores the maximum subarray sum ending at the current index where one deletion has already been used. 2. Start both states using the first element.

Initially:

• no_delete = arr[0]
• one_delete = 0

We also initialize the global answer with arr[0]. 3. Iterate through the array starting from index 1.

For each element arr[i], we compute updated states. 4. Update the one_delete state.

There are two possibilities:

• Delete the current element, which means taking the previous no_delete
• Keep the current element and extend a previous deleted-state subarray

Therefore:

one_delete = max(no_delete_previous, one_delete_previous + arr[i])

5. Update the no_delete state.

This is identical to Kadane’s algorithm.

Either:

• Start a new subarray at the current element
• Extend the previous subarray

So:

no_delete = max(arr[i], no_delete_previous + arr[i])

6. Update the global answer.

At each step, the best answer could come from either state. 7. Continue until the array is fully processed.

Why it works

The algorithm works because every valid subarray ending at index i falls into exactly one of two categories:

• No deletion has been used
• One deletion has already been used

The recurrence relations exhaust all valid transitions between these states. Since each state always stores the optimal value for its category, the final answer is guaranteed to be optimal.

Python Solution

from typing import List

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        no_delete = arr[0]
        one_delete = 0
        best_sum = arr[0]

        for i in range(1, len(arr)):
            current = arr[i]

            new_one_delete = max(no_delete, one_delete + current)
            new_no_delete = max(current, no_delete + current)

            one_delete = new_one_delete
            no_delete = new_no_delete

            best_sum = max(best_sum, no_delete, one_delete)

        return best_sum

The implementation follows the dynamic programming formulation directly.

The variable no_delete represents the best subarray ending at the current index without deletion. This is standard Kadane logic.

The variable one_delete represents the best subarray ending at the current index after deleting exactly one element somewhere earlier or at the current position.

Inside the loop, we first compute the new deleted-state value because it depends on the previous iteration’s values. Then we update the non-deleted state.

The global maximum is updated after every iteration because the optimal subarray may end anywhere in the array.

The solution uses constant extra space because only the previous state values are required.

Go Solution

func maximumSum(arr []int) int {
    noDelete := arr[0]
    oneDelete := 0
    bestSum := arr[0]

    for i := 1; i < len(arr); i++ {
        current := arr[i]

        newOneDelete := max(noDelete, oneDelete+current)
        newNoDelete := max(current, noDelete+current)

        oneDelete = newOneDelete
        noDelete = newNoDelete

        bestSum = max(bestSum, max(noDelete, oneDelete))
    }

    return bestSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation mirrors the Python version closely.

Go does not provide a built-in max function for integers, so we define one manually.

Since the constraints fit comfortably within Go’s int range, overflow is not an issue here.

The algorithm uses only a few integer variables, so memory usage remains constant.

Worked Examples

Example 1

Input:

arr = [1, -2, 0, 3]

Index	Value	no_delete	one_delete	best_sum
0	1	1	0	1
1	-2	-1	1	1
2	0	0	1	1
3	3	3	4	4

The optimal choice is deleting -2, giving subarray [1, 0, 3] with sum 4.

Example 2

Input:

arr = [1, -2, -2, 3]

Index	Value	no_delete	one_delete	best_sum
0	1	1	0	1
1	-2	-1	1	1
2	-2	-2	-1	1
3	3	3	3	3

The best result is simply [3].

Example 3

Input:

arr = [-1, -1, -1, -1]

Index	Value	no_delete	one_delete	best_sum
0	-1	-1	0	-1
1	-1	-1	-1	-1
2	-1	-1	-1	-1
3	-1	-1	-1	-1

The answer remains -1 because the subarray cannot become empty.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only constant extra variables are used

The algorithm processes each element exactly once. Every iteration performs only constant-time operations, so the overall runtime is linear.

The memory usage remains constant regardless of input size because no auxiliary arrays are created.

Test Cases

solution = Solution()

assert solution.maximumSum([1, -2, 0, 3]) == 4  # delete negative middle element
assert solution.maximumSum([1, -2, -2, 3]) == 3  # choose single positive
assert solution.maximumSum([-1, -1, -1, -1]) == -1  # all negatives
assert solution.maximumSum([5]) == 5  # single element
assert solution.maximumSum([1, 2, 3]) == 6  # no deletion needed
assert solution.maximumSum([1, -10, 2, 3]) == 6  # delete large negative
assert solution.maximumSum([0, 0, 0]) == 0  # all zeros
assert solution.maximumSum([8, -1, 6, -7, 3]) == 16  # delete internal negative
assert solution.maximumSum([-5]) == -5  # single negative
assert solution.maximumSum([2, 1, -2, -5, -2]) == 3  # deletion not always enough

Test	Why
[1, -2, 0, 3]	Standard deletion example
[1, -2, -2, 3]	Best subarray is a single element
[-1, -1, -1, -1]	All-negative handling
[5]	Single positive element
[1, 2, 3]	No deletion required
[1, -10, 2, 3]	Deleting a large negative improves result
[0, 0, 0]	Zero-valued array
[8, -1, 6, -7, 3]	Internal deletion case
[-5]	Single negative element
[2, 1, -2, -5, -2]	Complex negative sequence

Edge Cases

One important edge case is an array containing only negative numbers. A naive implementation might incorrectly return 0 by deleting all elements. However, the problem explicitly requires the resulting subarray to remain non-empty. The implementation avoids this mistake by initializing the answer with arr[0] instead of 0.

Another important case is a single-element array. Since there is no valid way to delete the only element while keeping the subarray non-empty, the answer must simply be that element itself. The algorithm naturally handles this because the loop never executes and the initial value is returned.

A third edge case occurs when deletion is not beneficial. For example, in [1, 2, 3], deleting any element would reduce the sum. The algorithm correctly keeps the normal Kadane state and allows the optimal answer to come from the non-deletion path.

LeetCode 1191 - K-Concatenation Maximum Sum

Problem Understanding

This problem asks us to compute the maximum subarray sum after repeating an array k times.

If:

arr = [1, 2]
k = 3

then the resulting array becomes:

[1, 2, 1, 2, 1, 2]

We must find the maximum possible contiguous subarray sum in this repeated array.

Unlike the previous problem, this one allows the subarray to be empty. That means the minimum possible answer is 0.

The answer may become very large, so we must return it modulo:

10^9 + 7

The constraints are large:

• arr.length up to 10^5
• k up to 10^5

Constructing the repeated array explicitly would be too expensive because its size could reach 10^10.

The challenge is to reason about the repeated structure mathematically instead of physically building the array.

Important edge cases include:

• Arrays with all negative values
• Very large k
• Arrays whose total sum is positive
• Arrays whose total sum is zero or negative
• Cases where the optimal subarray spans multiple copies

Approaches

Brute Force Approach

A brute-force method would explicitly build the concatenated array of length n * k, then run Kadane’s algorithm on it.

This works because Kadane’s algorithm correctly computes the maximum subarray sum.

However, this approach becomes impossible for large k. If both n and k are 10^5, the constructed array would contain 10^10 elements.

The memory and runtime costs are completely infeasible.

Optimal Dynamic Programming and Prefix-Suffix Insight

The crucial observation is that the optimal subarray can span at most two copies in a meaningful way unless the total array sum is positive.

There are two main cases:

• If the total array sum is non-positive, adding more copies does not help beyond considering two concatenations.
• If the total array sum is positive, then the middle copies contribute fully to the optimal answer.

The best result can therefore be expressed as:

max_prefix_sum + max_suffix_sum + (k - 2) * total_sum

when total_sum > 0.

We only need Kadane’s algorithm on at most two concatenated copies.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(n × k)	Explicitly constructs repeated array
Optimal	O(n)	O(1)	Uses Kadane plus prefix/suffix reasoning

Algorithm Walkthrough

1. Compute the total sum of the array.

This determines whether adding additional copies is beneficial. 2. Run Kadane’s algorithm on two concatenated copies of the array.

We only need at most two copies because any cross-boundary subarray must start in one copy and end in another. 3. If k == 1, return the Kadane result from one copy.

No additional concatenation exists. 4. If the total array sum is positive, additional middle copies increase the result.

In this case:

answer = max_two_copy_sum + (k - 2) * total_sum

5. If the total sum is non-positive, more copies do not help.

The answer is simply the maximum subarray sum within two copies. 6. Since empty subarrays are allowed, ensure the result is at least 0. 7. Return the result modulo 10^9 + 7.

Why it works

Any maximum subarray in the repeated structure either:

• Lies entirely within one copy
• Crosses one boundary between copies
• Or spans many copies

If the total sum is positive, including full middle copies always increases the total. Otherwise, adding more copies only reduces or preserves the sum.

This completely characterizes the optimal solution.

Python Solution

from typing import List

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        MOD = 10**9 + 7

        def kadane(nums: List[int]) -> int:
            current = 0
            best = 0

            for value in nums:
                current = max(0, current + value)
                best = max(best, current)

            return best

        total_sum = sum(arr)

        if k == 1:
            return kadane(arr) % MOD

        double_array = arr * 2
        best_two = kadane(double_array)

        if total_sum > 0:
            result = best_two + (k - 2) * total_sum
        else:
            result = best_two

        return result % MOD

The implementation begins with Kadane’s algorithm modified to allow empty subarrays. That is why the running sum never drops below 0.

We compute the total array sum because it determines whether additional copies contribute positively.

For k > 1, we run Kadane on two copies of the array. This captures every possible crossing subarray configuration.

If the total sum is positive, every fully included middle copy increases the result, so we add (k - 2) * total_sum.

Finally, we apply modulo arithmetic before returning.

Go Solution

func kConcatenationMaxSum(arr []int, k int) int {
    const MOD int = 1000000007

    kadane := func(nums []int) int {
        current := 0
        best := 0

        for _, value := range nums {
            current = max(0, current+value)
            best = max(best, current)
        }

        return best
    }

    totalSum := 0
    for _, value := range arr {
        totalSum += value
    }

    if k == 1 {
        return kadane(arr) % MOD
    }

    doubleArray := append(arr, arr...)
    bestTwo := kadane(doubleArray)

    result := bestTwo

    if totalSum > 0 {
        result += (k - 2) * totalSum
    }

    return result % MOD
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation follows the same logic as the Python version.

Slices are used naturally for concatenation with append(arr, arr...).

Integer overflow is not a concern under the given constraints when using Go’s standard int type on modern systems.

Modulo arithmetic is applied only at the end because intermediate values remain safely bounded.

Worked Examples

Example 1

Input:

arr = [1, 2]
k = 3

Total sum:

3

Two-copy array:

[1, 2, 1, 2]

Kadane trace:

Value	Current	Best
1	1	1
2	3	3
1	4	4
2	6	6

Then:

6 + (3 - 2) * 3 = 9

Answer:

9

Example 2

Input:

arr = [1, -2, 1]
k = 5

Total sum:

0

Two-copy array:

[1, -2, 1, 1, -2, 1]

Kadane result:

2

Since total sum is not positive, extra copies do not help.

Answer:

2

Example 3

Input:

arr = [-1, -2]
k = 7

Kadane with empty subarray allowed gives:

0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Kadane runs over at most two copies
Space	O(n)	Two-copy concatenation requires additional storage

The algorithm processes at most 2n elements, which is linear.

The extra space comes from building the doubled array. This can be optimized away by iterating twice manually, but the asymptotic complexity remains linear.

Test Cases

solution = Solution()

assert solution.kConcatenationMaxSum([1, 2], 3) == 9  # positive total sum
assert solution.kConcatenationMaxSum([1, -2, 1], 5) == 2  # zero total sum
assert solution.kConcatenationMaxSum([-1, -2], 7) == 0  # all negatives
assert solution.kConcatenationMaxSum([5], 1) == 5  # single positive
assert solution.kConcatenationMaxSum([-5], 1) == 0  # single negative with empty allowed
assert solution.kConcatenationMaxSum([0, 0, 0], 100) == 0  # all zeros
assert solution.kConcatenationMaxSum([2, 3], 100000) == 500000  # very large k
assert solution.kConcatenationMaxSum([1, -1, 1], 2) == 2  # crossing boundary
assert solution.kConcatenationMaxSum([10, -5, -5, 10], 3) == 30  # spanning copies
assert solution.kConcatenationMaxSum([1, 2, -100, 3, 4], 2) == 10  # optimal within two copies

Test	Why
[1, 2], k=3	Positive total sum
[1, -2, 1], k=5	Zero total sum
[-1, -2], k=7	Empty subarray behavior
[5], k=1	Single positive
[-5], k=1	Single negative
[0,0,0], k=100	Zero-only array
[2,3], k=100000	Large k stress case
[1,-1,1], k=2	Boundary crossing
[10,-5,-5,10], k=3	Multi-copy spanning
[1,2,-100,3,4], k=2	Mixed positive and negative

Edge Cases

One important edge case is an array containing only negative numbers. Since empty subarrays are allowed, the correct answer becomes 0. A standard Kadane implementation that forces non-empty subarrays would return a negative value incorrectly. The implementation avoids this by resetting the running sum to zero whenever it becomes negative.

Another important case occurs when the total array sum is positive. In this situation, additional copies meaningfully increase the answer because every full repeated block contributes positively. The implementation explicitly handles this with the (k - 2) * total_sum term.

A third edge case is very large values of k. Constructing the repeated array directly would cause memory exhaustion and unacceptable runtime. The implementation avoids this entirely by only considering at most two copies and using mathematical reasoning for the remaining repetitions.