@reagentx/

Subarray Sum O(n)

Python

No description

fork
loading
Files
  • main.py
main.py
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
35
36
37
38
39
40
41
def max_suabrray_sum(lst: list) -> int:
    # [-2, -3, 4, -1, -2, 1, 5, -3]
    max_so_far = 0
    max_ending_here = 0

    for i, v in enumerate(lst):
        max_ending_here += v

        if max_ending_here < 0:
            max_ending_here = 0

        if max_so_far < max_ending_here:
            max_so_far = max_ending_here

    return max_so_far


def max_suabrray_sum_neg(lst: list) -> int:
    max_so_far = 0
    max_ending_here = 0
    all_neg = True
    max_val = lst[0]

    for i, v in enumerate(lst):
        max_ending_here += v
        max_val = max(max_val, v)

        if v > 0:
            all_neg = False

        if max_ending_here < 0:
            max_ending_here = 0

        if max_so_far < max_ending_here:
            max_so_far = max_ending_here

    return max_so_far if not all_neg else max_val


print(max_suabrray_sum([-2, -3, 4, -1, -2, 1, 5, -3]))
print(max_suabrray_sum_neg([-2, -3, -4, -1, -2, -1, -5, -3]))