-
Notifications
You must be signed in to change notification settings - Fork 0
/
dac.py
65 lines (57 loc) · 1.85 KB
/
dac.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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import numpy as np
import math
import tracemalloc
import time
def find_max_crossing_subarray(a, low, mid, high):
max_sum = 0
left_sum = -math.inf
max_left = 0
for i in range(mid, low - 1, -1):
max_sum = max_sum + a[i]
if max_sum > left_sum:
left_sum = max_sum
max_left = i
max_sum = 0
right_sum = -math.inf
max_right = 0
for j in range(mid + 1, high + 1):
max_sum = max_sum + a[j]
if max_sum > right_sum:
right_sum = max_sum
max_right = j
return max_left, max_right, (left_sum + right_sum)
def find_maximum_subarray(a, low, high):
if high == low:
return low, high, a[low]
else:
mid = int((low + high) / 2)
(left_low, left_high, left_sum) = find_maximum_subarray(a, low, mid)
(right_low, right_high, right_sum) = find_maximum_subarray(a, mid + 1, high)
(cross_low, cross_high, cross_sum) = find_max_crossing_subarray(a, low, mid, high)
if left_sum >= right_sum and left_sum >= cross_sum:
return left_low, left_high, left_sum
elif right_sum >= left_sum and right_sum >= cross_sum:
return right_low, right_high, right_sum
else:
return cross_low, cross_high, cross_sum
#Generate an array (here size of 50000)
a = np.random.randint(-10, 10, 50000)
a = np.array(a)
#Start tracking memory
tracemalloc.start()
#Start tracking time
begin = time.time()
max_sum_subarray_dac = find_maximum_subarray(a, 0, len(a)-1)
#End tracking time
end = time.time()
#End tracking memory
snapshot= tracemalloc.take_snapshot()
for stat in snapshot.statistics("lineno"):
print("stat dac")
print(stat)
print(stat.traceback.format())
#Print memory peak
print("\nTraced Memory (Current, Peak): ", tracemalloc.get_traced_memory())
#Print time spent
print("Time:")
print(end-begin)