53. Maximum Subarray
Given an integer array
nums, find the
subarraywith the largest sum, and returnits sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Input: nums =  Output: 1 Explanation: The subarray  has the largest sum 1.
Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Follow up: If you have figured out the
O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
- Initialize a variable
maxSubarray = -infinityto keep track of the best subarray. We need to use negative infinity, not 0, because it is possible that there are only negative numbers in the array.
- Use a
forloop that considers each index of the array as a starting point.
- For each starting point, create a variable
currentSubarray = 0. Then, loop through the array from the starting index, adding each element to
currentSubarray. Every time we add an element it represents a possible subarray - so continuously update
maxSubarrayto contain the maximum out of the
class Solution: def maxSubArray(self, nums: List[int]) -> int: max_subarray = -math.inf for i in range(len(nums)): current_subarray = 0 for j in range(i, len(nums)): current_subarray += nums[j] max_subarray = max(max_subarray, current_subarray) return max_subarray
Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility. The difficult part of this problem is figuring out when a negative number is "worth" keeping in a subarray. This question in particular is a popular problem that can be solved using an algorithm called Kadane's Algorithm. If you're good at problem solving though, it's quite likely you'll be able to come up with the algorithm on your own. This algorithm also has a very greedy-like intuition behind it.
Let's focus on one important part: where the optimal subarray begins. We'll use the following example.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
We can see that the optimal subarray couldn't possibly involve the first 3 values - the overall sum of those numbers would always subtract from the total. Therefore, the subarray either starts at the first
4, or somewhere further to the right.
What if we had this example though?
nums = [-2,1000000000,-3,4,-1,2,1,-5,4]
We need a general way to figure out when a part of the array is worth keeping.
As expected, any subarray whose sum is positive is worth keeping. Let's start with an empty array, and iterate through the input, adding numbers to our array as we go along. Whenever the sum of the array is negative, we know the entire array is not worth keeping, so we'll reset it back to an empty array.
However, we don't actually need to build the subarray, we can just keep an integer variable
current_subarray and add the values of each element there. When it becomes negative, we reset it to 0 (an empty array).
Initialize 2 integer variables. Set both of them equal to the first value in the array.
currentSubarraywill keep the running count of the current subarray we are focusing on.
maxSubarraywill be our final return value. Continuously update it whenever we find a bigger subarray.
- Iterate through the array, starting with the 2nd element (as we used the first element to initialize our variables). For each number, add it to the
currentSubarraywe are building. If
currentSubarraybecomes negative, we know it isn't worth keeping, so throw it away. Remember to update
maxSubarrayevery time we find a new maximum.
A clever way to update
currentSubarray is using
currentSubarray = max(num, currentSubarray + num). If
currentSubarray is negative, then
num > currentSubarray + num.
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ current_subarray = nums max_subarray = nums # since current_subarray uses our first element for i in nums[1:]: # Work out whether or not we reset our current subarray # so if we go 1 6, -10 # we do not want to include -10, so we find the max here # equally if we go -10, -5, 6 # we want to start at 6 instead of -10 as it's higher current_subarray = max(i, current_subarray + i) # Our max subarray is the maximum between what we currently have vs the max we've found # since we do not need to remember which elements make up the max we can just store the value max_subarray = max(max_subarray, current_subarray) return max_subarray