Algorithm Code
Time: O(n) | Space: O(1)
1function maxSubArray(nums) {
2 let maxSum = nums[0];
3 let currSum = nums[0];
4 for (let i = 1; i < nums.length; i++) {
5 currSum = Math.max(nums[i], currSum + nums[i]);
6 maxSum = Math.max(maxSum, currSum);
7 }
8 return maxSum;
9}Algorithm Steps
Step 1 of 9
1
Start: currSum = maxSum = -2
2
At index 1: currSum = max(1, -2 + 1) = 1, maxSum = 1
3
At index 2: currSum = max(-3, 1 + -3) = -2, maxSum = 1
4
At index 3: currSum = max(4, -2 + 4) = 4, maxSum = 4
5
At index 4: currSum = max(-1, 4 + -1) = 3, maxSum = 4
6
At index 5: currSum = max(2, 3 + 2) = 5, maxSum = 5
7
At index 6: currSum = max(1, 5 + 1) = 6, maxSum = 6
8
At index 7: currSum = max(-5, 6 + -5) = 1, maxSum = 6
9
At index 8: currSum = max(4, 1 + 4) = 5, maxSum = 6
-2
1
-3
4
-1
2
1
-5
4
Current sum: -2
Max sum so far: -2
Step 0 of 80%
0.25x4x