-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.py
163 lines (128 loc) · 5.07 KB
/
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
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import random
import time
def brute_force_max_subarray(array):
length = len(array)
max_sum_index = (0, 0, 0)
max_sum = 0
for start in range(length):
sum = 0
for end in range(start, length):
sum += array[end]
if sum > max_sum:
max_sum = sum
max_sum_index = (max_sum, start, end)
return max_sum_index
def linear_time_max_subarray(array):
max_so_far = -10000
max_ending_here = -10000
start, end = 0, 0
for index in range(len(array)):
max_ending_here = max(array[index], max_ending_here + array[index])
if max_ending_here == array[index]:
start = index
if max_so_far < max_ending_here:
max_so_far = max_ending_here
end = index
final_start = start
return max_so_far, final_start, end
def max_crossing_subarray(array, l, m, h):
left_max_sum = -1000000
sum_l = 0
left_start_index = 0
for i in range(m, l - 1, -1):
sum_l = sum_l + array[i]
if sum_l > left_max_sum:
left_max_sum = sum_l
left_start_index = i
right_end_index = 0
sum_r = 0
right_max_sum = -100000
for j in range(m + 1, h + 1):
sum_r = sum_r + array[j]
if sum_r > right_max_sum:
right_max_sum = sum_r
right_end_index = j
return left_max_sum + right_max_sum, left_start_index, right_end_index
def divide_and_conquer_max_subarray(array, l, h):
m = int((h + l) / 2)
if l == h:
return array[l], l
return max(
divide_and_conquer_max_subarray(array, l, m),
divide_and_conquer_max_subarray(array, m + 1, h),
max_crossing_subarray(array, l, m, h)
)
def generate_random_array(number):
output = []
for i in range(number):
output.append(random.randint(-100,100))
return output
#array = [-2, -5, 6, -2, -3, 1, 5, -6]
array = [-2, 7, 6, -4, -2, -3, -1, -5, -6]
random_array = generate_random_array(100)
max_range = divide_and_conquer_max_subarray(random_array, 0, len(random_array) - 1)
max_range1 = linear_time_max_subarray(random_array)
max_range2 = brute_force_max_subarray(random_array)
def runningTimeComparison():
n_variations = [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]
# for setting the bounds of numbers for the randomly created array
array_num_lower_bound, array_num_upper_bound = -10000, 10000
# for storing the time elapsed while running the algorithm
linear_time_arr, brute_time_arr, divide_and_conquer_max_subarray_time_arr = [], [], []
for n in n_variations:
array = []
for _ in range(n):
array.append(random.randint(array_num_lower_bound, array_num_upper_bound))
start = time.time()
print("divide_and_conquer_max_subarray", n)
max_output = divide_and_conquer_max_subarray(array, 0, len(array) - 1)
end = time.time()
divide_and_conquer_max_subarray_time_arr.append(end - start)
start = time.time()
print("linear_time_max_subarray", n)
linear_output = linear_time_max_subarray(array)
end = time.time()
linear_time_arr.append(end - start)
start = time.time()
print("brute_force_max_subarray", n)
brute_output = brute_force_max_subarray(array)
end = time.time()
brute_time_arr.append(end - start)
print("divide_and_conquer_max_subarray_time_arr", divide_and_conquer_max_subarray_time_arr)
print("linear_time_arr", linear_time_arr)
print("brute_time_arr", brute_time_arr)
def maximumSubarray(array):
print("***********************")
start = time.time()
print("divide_and_conquer_max_subarray")
max_output = divide_and_conquer_max_subarray(array, 0, len(array) - 1)
end = time.time()
print("Max Sum:\t\t" + str(max_output[0]))
print("Indices:\t\t" + str(max_output[1]) + "-" + str(max_output[2]))
print("Max Subarray: \t" + str(array[max_output[1]:max_output[2]+1]))
print("Time Elapsed:\t" + str(end - start) + "s")
print("***********************")
start = time.time()
print("linear_time_max_subarray")
linear_output = linear_time_max_subarray(array)
end = time.time()
print("Max Sum:\t\t" + str(linear_output[0]))
print("Indices:\t\t" + str(linear_output[1]) + "-" + str(linear_output[2]))
print("Max Subarray: \t" + str(array[linear_output[1]:linear_output[2]+1]))
print("Time Elapsed:\t" + str(end - start) + "s")
print("***********************")
start = time.time()
print("brute_force_max_subarray")
brute_output = brute_force_max_subarray(array)
end = time.time()
print("Max Sum:\t\t" + str(brute_output[0]))
print("Indices:\t\t" + str(brute_output[1]) + "-" + str(brute_output[2]))
print("Max Subarray: \t" + str(array[brute_output[1]:brute_output[2]+1]))
print("Time Elapsed\t: " + str(end - start) + "s")
print("***********************")
a1 = [-2, -5, 6, -2, -3, 1, 5, -6]
a3 = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print("ARRAY 1")
maximumSubarray(a1)
print("ARRAY 3")
maximumSubarray(a3)