Maximum Subarray
- 1 min read
- Greedy
- LC-Medium
Solution
| Time | Space | Explanation |
|---|
O(n) | O(1) | |
def maxSubArray(self, nums: List[int]) -> int:
cur_sum, max_sum = 0, nums[0]
for num in nums:
cur_sum = max(cur_sum + num, num)
max_sum = max(cur_sum, max_sum)
return max_sum
