python/largest_contiguous_subvector.py at master · guimmp92/python · GitHub

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#!/usr/bin/python
# vim: foldlevel=0

"""
Given a vector x of n floating-point numbers (positive or negative), return the maximum
sum found in any contiguous subvector of the input. When all inputs are negative,
the maximum-sum subvector is the empty vector, which has sum zero.

Programming Pearls p77
"""


def algo1(x):
    """
    Calculate x[i:j] for each pair (i, j).
    Time complexity: O(n3)
    >>> algo1([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
    187
    >>> algo1([31, 41, 59, 26, 53, 58, 97, 93, 23, 84])
    565
    >>> algo1([31])
    31
    >>> algo1([-31])
    0
    """
    maxsofar = 0
    for i in range(len(x)):
        for j in range(len(x[i:])):
            cursum = sum(x[i:j+1])
            maxsofar = max(maxsofar, cursum)
    return maxsofar


def algo2(x):
    """
    Calculate x[i:j] for each pair (i, j) without summing interval on every pass.
    Time complexity: O(n2)
    >>> algo2([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
    187
    >>> algo2([31, 41, 59, 26, 53, 58, 97, 93, 23, 84])
    565
    >>> algo2([31])
    31
    >>> algo2([-31])
    0
    """
    rollingsum = [0] * (len(x)+1)
    for i in range(len(x)):
        rollingsum[i+1] = rollingsum[i] + x[i]

    maxsofar = 0
    for i in range(len(x)):
        cursum = 0
        for j in range(i, len(x)):
            cursum = rollingsum[j+1] - rollingsum[i]
            maxsofar = max(maxsofar, cursum)

    return maxsofar


def find_largest_subvector(x, left, right):
    if left > right:
        return 0
    if left == right:
        return max(x[left], 0)

    middle = (left+right)//2
    leftmax, rightmax = 0, 0
    cursum = 0
    for elem in reversed(x[left:middle]):
        cursum += elem
        leftmax = max(leftmax, cursum)
    cursum = 0
    for elem in x[middle:right+1]:
        cursum += elem
        rightmax = max(rightmax, cursum)

    return max(leftmax+rightmax,
               find_largest_subvector(x, left, middle-1),
               find_largest_subvector(x, middle+1, right))


def algo3(x):
    """
    Time complexity: O(nlog(n))
    >>> algo3([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
    187
    >>> algo3([31, 41, 59, 26, 53, 58, 97, 93, 23, 84])
    565
    >>> algo3([31])
    31
    >>> algo3([-31])
    0
    """
    return find_largest_subvector(x, 0, len(x)-1)


def algo4(x):
    """
    Time complexity: O(n)
    >>> algo4([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
    187
    >>> algo4([31, 41, 59, 26, 53, 58, 97, 93, 23, 84])
    565
    >>> algo4([31])
    31
    >>> algo4([-31])
    0
    """
    maxsofar = 0
    maxendinghere = 0
    for i in range(len(x)):
        maxendinghere = max(maxendinghere + x[i], 0)
        maxsofar = max(maxsofar, maxendinghere)
    return maxsofar


def dp(A, j, memo):
    if memo[j] == -1:
        if j == 0:
            memo[j] = max(A[j], 0)
        else:
            memo[j] = max(dp(A, j-1, memo)+A[j], A[j])
    return memo[j]


def algo5(A):
    """
    Time complexity: O(n)
    >>> algo5([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
    187
    >>> algo5([31, 41, 59, 26, 53, 58, 97, 93, 23, 84])
    565
    >>> algo5([31])
    31
    >>> algo5([-31])
    0
    """
    memo = [-1] * len(A)
    dp(A, len(A)-1, memo)
    return max(memo)


if __name__ == "__main__":
    import doctest
    doctest.testmod()