Given an integer array
nums, find the
subarray with the largest sum, and return its 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
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
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 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
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
i = 1, the possible sub arrays are
[-2, 1] with sub array sums of
-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.
class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) dp =  * n dp = nums ans = nums """ -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