Problem Statement
Description
Given an integer array nums, find the
subarray with the largest sum, and return its sum.
Examples
Example 1:
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.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints
1 <= nums.length <= 105-104 <= nums[i] <= 104
Key Insights
In a real interview, it’s a very good idea to discuss the brute force solution first. Starting with the quick and dirty solution demonstrates that you know how to solve problems as opposed to just recite solutions.
Since we’re embracing the messy approach, let’s jump into the weeds and see what we can come up with. We know that we will need to traverse the nums array at least once. While we are at each index i, we need to figure out a way of determining each sub array sum that ends at i.
What if we looped back to beginning from each index i and calculated all of the possible sub array sums. We could keep track of each sum and store the result in a final answer ans variable. This would give us an O(N2) solution that we could optimize. See the following code.
def maxSubArray(nums: List[int]) -> int:
n = len(nums)
ans = nums[0]
sub = 0
for i in range(n):
for j in range(i, -1, -1):
sub += nums[j]
ans = max(ans, sub)
sub = 0
return ans
This brute force approach is a good start, but it won’t get you the job. We’re going to need to do better! As we evaluate this problem, we notice that we are redoing a lot of work each time we calculate the the sub array sums. We also recognize that the solution to the overall problem can be solved by using the results of smaller subproblems. This looks like a Dynamic Programming problem!
Let’s start with the smallest possible subproblem and see what we can come up with. In the following example, the sum of the sub array ending at index i = 0 is -2.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
At i = 1, the possible sub arrays are [1] and [-2, 1] with sub array sums of 1 and -1 respectively. At i=0, the largest sub array sum is ans = -2; and at i = 1, the largest sub array sum is ans = 1. If we know the sub array sum at i = 0, we can find the sub array sum at i = 1.
Since we are looking for the largest sub array sum in the array, we can actually make a choice at each index i. If the adding nums[i] to the running sub array sum results in a value that is larger than nums[i], we can continue to build out the current sub array. However, if nums[i] is greater than the sub array that can be created by adding nums[i] to the current running total, we start a new sub array at index i, whose new sub array sum is nums[i]. In so doing, we can actually solve the problem in one pass.
If we maintain a dp array, we can store the sum of the largest sub array sum that ends at index i. As we traverse through the nums array, we can maintain an ans variable to store the value of the largest overall sub array sum.
Python Solution
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
ans = nums[0]
"""
-2, 1, -3, 4, -1, 2, 1, -5, 4
^
"""
for i in range(1, n):
dp[i] = max(dp[i-1] + nums[i], nums[i])
ans = max(ans, dp[i])
return ans
Manual Execution
| i | nums | dp | ans |
|---|---|---|---|
0 | -2 | -2 | -2 |
1 | 1 | 1 | 1 |
2 | -3 | -2 | 1 |
3 | 4 | 4 | 4 |
4 | -1 | 3 | 4 |
5 | 2 | 5 | 5 |
6 | 1 | 6 | 6 |
7 | -5 | 1 | 6 |
8 | 4 | 5 | 6 |