29
loading...
Leetcode: Maximum Subarray
This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.
If you liked this solution or found it useful, please like this post.
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Input: nums = [1]
Output: 1
Input: nums = [5,4,-1,7,8]
Output: 23
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
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.
This problem can be complex and simple according to how you approach it.
Can we find out the pattern to find the max sum possible using a sub-array, say we have a list like 1, 2, 3, 4
the max sum possible would be 10 right ?
So can we say that starting from index 0
- max sum upto index 0 = 1
- max sum upto index 2 = 3
- max sum upto index 3 = 6
- max sum upto index 4 = 10
let's add some fun then!
now the list is 1, -2, 3, 4
previous MaxSum or current Value +previous MaxSum? = 1
so, we can see that even if we summed all the digits, the values comes out to be 8.
let's go for the worse case
-2, 1, -3, 4, -1, 2, 1, -5, 4
-2, 1, -3, 4, -1, 2, 1, -5, 4
-2 vs 1+-2 = -1 wait, this doesn't look right, if we have a positive number already, why do we have max sum = -1
ok, lets add another layer of check,
max = max(num[i], num[i-1]+num[i], maxSum)
- max sum upto index 1 =
-2 vs 1+-2 vs 1= 1!
1 vs -3 vs -3 = 11 vs 4-3 vs 4 = 44 vs -1+4 vs -1 = 44 vs 2-1 vs 2 = 4 - wait again no! a series of 4, -1, 2 is ok, we can't just take the last two values, we need a concept of localSum. So
now
localMaxSum = nums[i] + Math.max(0, localMaxSum);
- max sum upto index 1 =
4 vs -1+2+4 vs 2= 5!
5 vs 5+1 vs 1 = 66 vs 6-5 vs -5 = 66 vs 6-5+4 vs 4 = 6public static int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxSum = nums[0];
int localMaxSum = nums[0];
for (int i = 1, numsLength = nums.length; i < numsLength; i++) {
localMaxSum = nums[i] + Math.max(0, localMaxSum);
maxSum = Math.max(maxSum, localMaxSum);
}
return maxSum;
}
}
29