LeetCode - Maximum Subarray
Problem statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Problem statement taken from: https://leetcode.com/problems/maximum-subarray
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 = [5, 4, -1, 7, 8]
Output: 23
Constraints:
- 1 <= nums.length <= 3 * 10^4
- -10^5 <= nums[i] <= 10^5
Explanation
Brute force
The brute force approach is to generate all subarrays and print that subarray which has a maximum sum.
A C++ snippet of the above logic is as below:
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
for (int k = i; k <= j; k++){
// calculate sum of all the elements
}
}
}The time complexity of the above approach is O(N^3). We can improve the above logic using Kadane algorithm.
Kadane algorithm
The simple idea of Kadane’s algorithm is to look for all positive contiguous segments
of the array (max_sum is used for this).
And keep track of maximum sum contiguous segment among all positive segments
(max_sum_so_far is used for this).
Each time we get a positive sum compare it with max_sum and
update max_sum if it is greater than max_sum_so_far.
Let's check the algorithm below:
- set max_sum_so_far = 0, max_sum = INT_MIN
- Loop for i = 0; i < nums.length; i++
- add max_sum_so_far = max_sum_so_far + nums[i]
- if max_sum < max_sum_so_far
- set max_sum = max_sum_so_far
- if max_sum_so_far < 0
- set max_sum_so_far = 0
- return max_sum
The time complexity of the above approach is O(N) and, space complexity is O(1).
C++ solution
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum = INT_MIN;
int max_sum_so_far = 0;
for(int i = 0; i < nums.size(); i++){
max_sum_so_far += nums[i];
if(max_sum < max_sum_so_far){
max_sum = max_sum_so_far;
}
if(max_sum_so_far < 0){
max_sum_so_far = 0;
}
}
return max_sum;
}
};Golang solution
func maxSubArray(nums []int) int {
maxSum := math.MinInt32
maxSumSoFar := 0
for i := 0; i < len(nums); i++ {
maxSumSoFar += nums[i]
if maxSum < maxSumSoFar {
maxSum = maxSumSoFar
}
if maxSumSoFar < 0 {
maxSumSoFar = 0
}
}
return maxSum
}Javascript solution
var maxSubArray = function(nums) {
let maxSumSoFar = 0;
let maxSum = -Infinity;
if(nums.length === 0) return 0;
if(nums.length === 1) return nums[0]
for( let i = 0; i<nums.length; i++) {
maxSumSoFar += nums[i];
maxSum = Math.max(maxSum, maxSumSoFar);
if(maxSumSoFar < 0) {
maxSumSoFar = 0;
}
}
return maxSum;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Step 1: max_sum_so_far = 0
max_sum = INT_MIN
Step 2: for i = 0; i < nums.length
0 < 9
true
max_sum_so_far += nums[0]
max_sum_so_far = 0 + -2
max_sum_so_far = -2
max_sum < max_sum_so_far
-2^31 - 1 < -2
true
max_sum = max_sum_so_far
max_sum = -2
max_sum_so_far < 0
-2 < 0
true
max_sum_so_far = 0
i++
i = 1
Step 3: i < nums.length
1 < 9
true
max_sum_so_far += nums[1]
max_sum_so_far = 0 + 1
max_sum_so_far = 1
max_sum < max_sum_so_far
-2 < 1
true
max_sum = max_sum_so_far
max_sum = 1
max_sum_so_far < 0
1 < 0
false
i++
i = 2
Step 4: i < nums.length
2 < 9
true
max_sum_so_far += nums[2]
max_sum_so_far = 1 + -3
max_sum_so_far = -2
max_sum < max_sum_so_far
1 < -2
false
max_sum_so_far < 0
-2 < 0
true
max_sum_so_far = 0
i++
i = 3
Step 5: i < nums.length
3 < 9
true
max_sum_so_far += nums[3]
max_sum_so_far = 0 + 4
max_sum_so_far = 4
max_sum < max_sum_so_far
1 < 4
true
max_sum = max_sum_so_far
max_sum = 4
max_sum_so_far < 0
false
i++
i = 4
Step 6: i < nums.length
4 < 9
true
max_sum_so_far += nums[4]
max_sum_so_far = 4 + -1
max_sum_so_far = 3
max_sum < max_sum_so_far
4 < 3
false
max_sum_so_far < 0
false
i++
i = 5
Step 7: i < nums.length
5 < 9
true
max_sum_so_far += nums[5]
max_sum_so_far = 3 + 2
max_sum_so_far = 5
max_sum < 5
4 < 5
true
max_sum = max_sum_so_far
max_sum = 5
max_sum_so_far < 0
false
i++
i = 6
Step 8: i < nums.length
6 < 9
true
max_sum_so_far += nums[6]
max_sum_so_far = 5 + 1
max_sum_so_far = 6
max_sum < 6
5 < 6
true
max_sum = max_sum_so_far
max_sum = 6
max_sum_so_far < 0
false
i++
i = 7
Step 9: i < nums.length
7 < 9
true
max_sum_so_far += nums[7]
max_sum_so_far = 6 + -5
max_sum_so_far = 1
max_sum < 6
6 < 1
false
max_sum_so_far < 0
false
i++
i = 8
Step 10: i < nums.length
8 < 9
true
max_sum_so_far += nums[8]
max_sum_so_far = 1 + 4
max_sum_so_far = 5
max_sum < 6
6 < 5
false
max_sum_so_far < 0
false
i++
i = 9
Step 11: i < nums.length
9 < 9
false
Step 12: return max_sum
Answer is 6