time Varies
space Varies
State Variables
currSum-
maxSum-
-2
[0]
1
[1]
-3
[2]
4
[3]
-1
[4]
2
[5]
1
[6]
-5
[7]
4
[8]
Initialize maxSum to negative infinity.
Pseudocode
Pseudocode
1function maxSubArray(nums):
2 maxSum = -Infinity
3 for i = 0 to nums.length - 1:
4 currentSum = 0
5 for j = i to nums.length - 1:
6 currentSum += nums[j]
7 if currentSum > maxSum:
8 maxSum = currentSum
9 return maxSum