Introduction

The greatest sum of a continuous subset is the classic maximum-subarray problem. The standard version is solved by Kadane's algorithm in linear time, but real interview and production variants often add conditions such as all-negative input, mandatory minimum length, or one allowed deletion. Once the condition changes, the simple textbook answer often needs a small but important redesign.

Start with the Classic Maximum Subarray

For the unrestricted version, Kadane's algorithm is the right baseline. It keeps track of the best sum ending at the current position and the best sum seen overall.

1def max_subarray(nums):
2    best = nums[0]
3    current = nums[0]
4
5    for value in nums[1:]:
6        current = max(value, current + value)
7        best = max(best, current)
8
9    return best
10
11print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

This runs in O(n) time and O(1) extra space. The crucial detail is that each step decides whether to extend the current subarray or start a new one.

Handle the All-Negative Case Correctly

A common bug is initializing the running sum to zero and resetting whenever it becomes negative. That version returns zero for an all-negative array, which is wrong if the problem requires at least one element to be chosen.

The earlier implementation avoids that problem because it starts from nums[0], not from zero.

print(max_subarray([-8, -3, -6, -2, -5, -4]))  # -2

That is the right answer because the best continuous subset is just [-2].

Add a Minimum Length Constraint

If the subarray must have at least k elements, plain Kadane is no longer enough. One practical approach is to combine prefix sums with a running minimum prefix.

1def max_subarray_at_least_k(nums, k):
2    prefix = [0]
3    for value in nums:
4        prefix.append(prefix[-1] + value)
5
6    best = float("-inf")
7    min_prefix = 0
8
9    for i in range(k, len(prefix)):
10        min_prefix = min(min_prefix, prefix[i - k])
11        best = max(best, prefix[i] - min_prefix)
12
13    return best
14
15print(max_subarray_at_least_k([1, -2, 3, 4, -1, 2], 2))

This works because the sum of a subarray is a difference of prefix sums, and the minimum-length rule determines how far back the start is allowed to move.

Allow One Deletion Inside the Subarray

Another common variant asks for the best continuous subset if you may delete at most one element. This is not the same as skipping an element at the ends. The deletion may happen in the middle to connect two strong segments.

1def max_subarray_one_deletion(nums):
2    keep = nums[0]
3    drop = float("-inf")
4    best = nums[0]
5
6    for value in nums[1:]:
7        drop = max(drop + value, keep)
8        keep = max(value, keep + value)
9        best = max(best, keep, drop)
10
11    return best
12
13print(max_subarray_one_deletion([1, -2, 0, 3]))

Here:

1. keep means best sum ending here with no deletion used.
2. drop means best sum ending here after one deletion has been used.

This is still linear time, but the state now reflects the condition change explicitly.

Distinguish Continuous from Arbitrary Subset

The word “continuous” or “contiguous” changes the whole problem. If continuity is required, you cannot freely choose all positive numbers. That would be a subset problem, not a maximum-subarray problem.

For example, in [5, -100, 6]:

1. Best arbitrary subset sum is 11.
2. Best continuous subset sum is 6.

Many mistakes come from silently switching between those two meanings.

Use the Condition to Choose the State

A good way to think about these variants is:

1. What does the best answer ending at position i need to remember.
2. What extra state does the condition add.

For the classic problem, the state is just the best sum ending here. For one deletion, you need two states. For minimum length, prefix sums become more natural. Once the condition is translated into state, the implementation usually becomes much clearer.

Common Pitfalls

• Initializing Kadane's algorithm with zero and returning the wrong result for all-negative arrays.
• Confusing a continuous subset with an arbitrary subset of positive numbers.
• Reusing the classic formula unchanged when a minimum length or deletion condition has been added.
• Forgetting that exactly-one-deletion and at-most-one-deletion are different problems.
• Optimizing too early before identifying what state the new condition really requires.

Summary

• The classic greatest-sum continuous subset problem is solved by Kadane's algorithm in linear time.
• All-negative arrays require careful initialization so at least one element is chosen.
• Extra conditions such as minimum length or one deletion change the required dynamic-programming state.
• Prefix sums are useful for length-constrained versions.
• The fastest route to the correct algorithm is to define the condition clearly before choosing the recurrence.