Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
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.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [0] Output: 0
Example 4:
Input: nums = [-1] Output: -1
Example 5:
Input: nums = [-2147483647] Output: -2147483647
Constraints:
1 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 1
Description taken from https://leetcode.com/problems/maximum-subarray/.
#O(N) Time, O(1) Spaceclass Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range (1, len(nums)): if nums[i-1] > 0: nums[i] += nums[i-1] return max(nums)This question is a good introduction to dynamic programming. It doesn't follow a traditional dynamic programming approach, but it follows a similar intuition. Bottom-up dynamic programming is done by the use of tabulation. Through tabulation, we would typically break the problem down into subproblems for each index. By the time we have reached the final index, we have solved our overall problem. Here, we can use Kadane's Algorithm to solve the problem.
The strategy remains the same though, for each previous index, which will be each subproblem, we will see if it is non-negative. If it is, we can combine the results of these two subproblems because we know that at least these two elements will be non-negative and will form a subarray that would sum to a value greater than two negative values would.
Once we have finished traversing the array, we will return the tabulated snowball sum that was greater than all of the others.
We will start by traversing the array starting from the second index and during each iteration, we will check if the previous element is non-negative.
for i in range (1, len(nums)): if nums[i-1] > 0:
If it is, we will sum that element with our current element and continue.
nums[i] += nums[i-1]
Once we are out of the loop and have traversed the array, we will return the max element. This would be the maximum sum out of all the contiguous subarrays.
return max(nums)
Kadane's Algorithm is one of the popular ones that we'll want in our toolbelt. This may seem like a trivial formula, but we can apply this algorithm to many questions to find a subarray with the greatest constraint.