| 5 | # like sliding window O(n) - linear time algorithm |
| 6 | # we only have to return maxSubaaray value not the subarray |
| 7 | class Solution: |
| 8 | def maxSubArray(self, nums: list[int]) -> int: |
| 9 | maxSub = nums[0] |
| 10 | curSum = 0 |
| 11 | for n in nums: |
| 12 | if curSum < 0: |
| 13 | curSum = 0 |
| 14 | curSum += n |
| 15 | maxSub = max(maxSub, curSum) |
| 16 | return maxSub |
| 17 | print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) |
| 18 | print(Solution().maxSubArray([1,2,3,4,5,6,7,8,9,10])) |