Skip to content

Commit 906b91d

Browse files
committed
more pythonic iteration; positive -> non-negative in the description; added test with all negative numbers
1 parent 02ec2ec commit 906b91d

1 file changed

Lines changed: 10 additions & 9 deletions

File tree

‎Dynamic Programming/max_subarray_sum.py‎

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
1010
=========================================
1111
Need only one iteration, in each step add the current element to the current sum.
12-
When the sum is equal or less than 0, reset the sum to 0 and continue with adding. (we care only about the positive sums)
12+
When the sum is less than 0, reset the sum to 0 and continue with adding. (we care only about non-negative sums)
1313
After each addition, check if the current sum is greater than the max sum. (Called Kadane's algorithm)
1414
Time Complexity: O(N)
1515
Space Complexity: O(1)
@@ -21,20 +21,17 @@
2121
############
2222

2323
def max_subarray_sum(a):
24-
i = 0
25-
n = len(a)
2624
curr_sum = 0
2725
max_sum = 0
2826

29-
while i < n:
30-
# restart the current sum if 0 or smaller, we care only about the positive sums
31-
curr_sum = max(0, curr_sum + a[i])
27+
for val in a:
28+
# extend the current sum with the curren value;
29+
# reset it to 0 if it is smaller than 0, we care only about non-negative sums
30+
curr_sum = max(0, curr_sum + val)
3231

3332
# check if this is the max sum
3433
max_sum = max(max_sum, curr_sum)
3534

36-
i += 1
37-
3835
return max_sum
3936

4037

@@ -52,4 +49,8 @@ def max_subarray_sum(a):
5249

5350
# Test 3
5451
# Correct result => 7
55-
print(max_subarray_sum([-2, -5, 6, -2, -3, 1, 5, -6]))
52+
print(max_subarray_sum([-2, -5, 6, -2, -3, 1, 5, -6]))
53+
54+
# Test 4
55+
# Correct result => 0
56+
print(max_subarray_sum([-6, -1]))

0 commit comments

Comments
 (0)