forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdusunax.py
More file actions
34 lines (24 loc) · 804 Bytes
/
dusunax.py
File metadata and controls
34 lines (24 loc) · 804 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
'''
# 53. Maximum Subarray
- use Kadane's Algorithm for efficiently finding the maximum subarray sum.
## Time and Space Complexity
```
TC: O(n)
SC: O(1)
```
#### TC is O(n):
- iterating through the list just once to find the maximum subarray sum. = O(n)
#### SC is O(1):
- using a constant amount of extra space to store the current sum and the maximum sum. = O(1)
'''
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
currentSum = 0 # SC: O(1)
maxSum = nums[0] # SC: O(1)
for i in range(len(nums)): # TC: O(n)
currentSum = max(currentSum + nums[i], nums[i]) # TC: O(1)
if currentSum > maxSum: # TC: O(1)
maxSum = currentSum
return maxSum