Given an integer array
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Give it a try.
If you really wanna see the solution scroll down.
We can solve this problem by brute force. We'll find every possible subarray and it's sum. The runtime for this approach will be O(n2).
def maxSubArray(nums): maxSum = nums for i in range(len(nums)): currSum = nums[i] for j in range(i+1, len(nums)): currSum = currSum + nums[j] if(maxSum < currSum): maxSum = currSum return maxSum
This is the poster boy question of Dynamic programming. In this approach we'll use the Kagane's algorithm. Please check this awesome video tutorial for Kagane's algorithm.
Basically this problem can be divided in smaller sub problems. Here the sub problem will be to find the maximum subarray ending at all indexes and finding the maximum of it.
To find the maximum sub array ending at ith index. We can take max of following.
- Extend the trailing subarray and adding ith element to it.
- New subarray consisting of only ith element.
So we can find the maximum sub array ending at ith index as.
maxSubArrSum = max( maxSubArrSum(i-1) + nums[i], nums[i])
We'll do this in O(n) time and space.
def maxSubArrayDP(nums): maxSubArraySum = [None] * len(nums) currMaxSum = nums for i in range(1, len(nums)): currMaxSum = max(nums[i] + currMaxSum, nums[i]) maxSubArraySum[i] = currMaxSum return max(maxSubArraySum)
We can improvise the above solution and save some space. We can solve this in constant space. Instead of saving the maximum sum for every element we can save the maximum of all the elements visited till now.
def maxSubArray(nums): maxSum = nums currMaxSum = nums for i in range(1, len(nums)): currMaxSum = max(nums[i] + currMaxSum, nums[i]) maxSum = max(currMaxSum, maxSum) return maxSum