Maximum Subarray

mediumFREEGreedyBlind 75

Given an integer array, find the subarray with the largest sum and return its sum.

Example

Input

-2,1,-3,4,-1,2,1,-5,4

Output

Reasoning

Input: nums is a list of integers, here -2,1,-3,4,-1,2,1,-5,4. A subarray is a contiguous, non-empty run $nums_i, nums_{i+1}, \dots, nums_j$ .
Math: each run has sum $S(i, j) = \sum_{k=i}^{j} nums_k$ , and the answer is the largest $S(i, j)$ over all $i \le j$ .
The best run is indices $3$ to $6$ : $4 + (-1) + 2 + 1 = 6$ . The $-1$ is worth keeping because it connects $4$ to $2 + 1 = 3$ , and $4 - 1 + 3 = 6$ beats $4$ alone or $3$ alone.
Stretching it further only hurts: the values before it, $-2 + 1 + (-3) = -4$ , and after it, $-5 + 4 = -1$ , both add a negative amount.
Output: a single integer, 6. Notice that adding up just the positive values ( $1+4+2+1+4 = 12$ ) is not allowed — they are not contiguous. If every value were negative, the answer would be the single largest (least negative) element, since the run cannot be empty.

Constraints

1 <= len(nums) <= 10^5
-10^4 <= nums[i] <= 10^4

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The Maximum Subarray problem is a classic problem in the realm of arrays and dynamic programming. To tackle this problem, it's essential to understand the concept of a subarray, which is a contiguous subset of elements within an array. The goal is to find the subarray with the largest sum, which can be achieved by considering all possible subarrays and calculating their sums. This problem requires a deep understanding of array manipulation and iterative techniques.

The key concept to grasp here is that the maximum sum of a subarray can be obtained by either including or excluding the current element from the previous subarray. This idea is rooted in dynamic programming, where we break down the problem into smaller sub-problems and store the solutions to these sub-problems to avoid redundant calculations. In the context of the Maximum Subarray problem, we can utilize this concept to efficiently compute the maximum sum of all possible subarrays.

Another crucial aspect to consider is the trade-off between time and space complexity. A naive approach might involve calculating the sum of all possible subarrays, resulting in a time complexity of $O(n^3)$ , where $n$ is the number of elements in the array. However, by leveraging dynamic programming and iterative techniques, we can significantly reduce the time complexity while maintaining a reasonable space complexity.

Algorithm/Approach

The Kadane's algorithm is a popular approach to solve the Maximum Subarray problem. This algorithm iterates through the array, at each step deciding whether to include the current element in the maximum subarray or start a new subarray. The algorithm maintains a running sum of the maximum subarray ending at the current position and updates it accordingly.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize variables to store the maximum sum and the current sum.
Iterate through the array, considering each element as a potential starting point for the maximum subarray.
At each step, calculate the sum of the subarray ending at the current position by adding the current element to the previous sum.
Update the maximum sum if the current sum is greater.
If the current sum becomes negative, reset it to the current element, as a negative sum has no benefit in contributing to the maximum sum.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrect initialization of variables, leading to incorrect results.
Failure to update the maximum sum correctly, resulting in an incorrect answer.
Not handling edge cases, such as an empty array or an array with a single element.

Time & Space Complexity

The expected time complexity for the Maximum Subarray problem is $O(n)$ , where $n$ is the number of elements in the array. This is because we only need to iterate through the array once to find the maximum sum. The space complexity is $O(1)$ , as we only need to store a constant amount of information, regardless of the size of the input array.

solution.py

Python 3.13

Test results