-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathmax_subarray_problem.py
More file actions
100 lines (90 loc) · 5.08 KB
/
Copy pathmax_subarray_problem.py
File metadata and controls
100 lines (90 loc) · 5.08 KB
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
#!/usr/bin/env python
inf = float('inf')
def find_max_crossing_subarray(a, low, mid, high):
max_left = max_right = mid
left_sum = -inf
sum = 0
for i in range(mid, low - 1, -1):
sum += a[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = -inf
sum = 0
for j in range(mid + 1, high + 1):
sum += a[j]
if sum > right_sum:
right_sum = sum
max_right = j
return max_left, max_right, left_sum + right_sum
def find_maximum_subarray(a, low, high):
if low == high:
return low, high, a[low]
else:
mid = (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
if __name__ == "__main__":
b = [-1, -202, -293, -60, -261, -67, 10, 82, -334, -393, -428, -182, -138, -167, -465, -347, -39, -51, -61, -491,
-216, -36,
-281, -361, -271, -368, -122, -114, -53, -488, -327, -182, -221, -381, -431, -161, -59, -494, -406, -298, -268,
-425, -88,
-320, -371, -5, 36, 89, -194, -140, -278, -65, -38, -144, -407, -235, -426, -219, 62, -299, 1, -454, -247,
-146, 24, 2, -59,
-389, -77, -19, -311, 18, -442, -186, -334, 41, -84, 21, -100, 65, -491, 94, -346, -412, -371, 89, -56, -365,
-249, -454,
-226, -473, 91, -412, -30, -248, -36, -95, -395, -74, -432, 47, -259, -474, -409, -429, -215, -102, -63, 80,
65, 63, -452,
-169, -418, 63, 77, 77, -197, -49, -150, -37, -493, -284, -107, 93, -183, -60, -261, -310, -380]
ar = [-120, -202, -293, -60, -261, -67, 10, 82, -334, -393, -428, -182, -138, -167, -465, -347, -39, -51, -61, -491,
-216, -36,
-281, -361, -271, -368, -122, -114, -53, -488, -327, -182, -221, -381, -431, -161, -59, -494, -406, -298, -268,
-425, -88,
-320, -371, -5, 36, 89, -194, -140, -278, -65, -38, -144, -407, -235, -426, -219, 62, -299, 1, -454, -247,
-146, 24, 2, -59,
-389, -77, -19, -311, 18, -442, -186, -334, 41, -84, 21, -100, 65, -491, 94, -346, -412, -371, 89, -56, -365,
-249, -454,
-226, -473, 91, -412, -30, -248, -36, -95, -395, -74, -432, 47, -259, -474, -409, -429, -215, -102, -63, 80,
65, 63, -452,
-462, -449, 87, -319, -156, -82, 30, -102, 68, -472, -463, -212, -267, -302, -471, -245, -165, 43, -288, -379,
-243, 35,
-288, 62, 23, -444, -91, -24, -110, -28, -305, -81, -169, -348, -184, 79, -262, 13, -459, -345, 70, -24, -343,
-308, -123,
-310, -239, 83, -127, -482, -179, -11, -60, 35, -107, -389, -427, -210, -238, -184, 90, -211, -250, -147, -272,
43, -99, 87,
-267, -270, -432, -272, -26, -327, -409, -353, -475, -210, -14, -145, -164, -300, -327, -138, -408, -421, -26,
-375, -263, 7,
-201, -22, -402, -241, 67, -334, -452, -367, -284, -95, -122, -444, -456, -152, 25, 21, 61, -320, -87, 98, 16,
-124, -299,
-415, -273, -200, -146, -437, -457, 75, 84, -233, -54, -292, -319, -99, -28, -97, -435, -479, -255, -234, -447,
-157, 82,
-450, 86, -478, -58, 9, -500, -87, 29, -286, -378, -466, 88, -366, -425, -38, -134, -184, 32, -13, -263, -371,
-246, 33,
-41, -192, -14, -311, -478, -374, -186, -353, -334, -265, -169, -418, 63, 77, 77, -197, -211, -276, -190, -68,
-184, -185,
-235, -31, -465, -297, -277, -456, -181, -219, -329, 40, -341, -476, 28, -313, -78, -165, -310, -496, -450,
-318, -483,
-22, -84, 83, -185, -140, -62, -114, -141, -189, -395, -63, -359, 26, -318, 86, -449, -419, -2, 81, -326, -339,
-56, -123,
10, -463, 41, -458, -409, -314, -125, -495, -256, -388, 75, 40, -37, -449, -485, -487, -376, -262, 57, -321,
-364, -246,
-330, -36, -473, -482, -94, -63, -414, -159, -200, -13, -405, -268, -455, -293, -298, -416, -222, -207, -473,
-377, -167,
56, -488, -447, -206, -215, -176, 76, -304, -163, -28, -210, -18, -484, 45, 10, 79, -441, -197, -16, -145,
-422, -124, 79,
-464, -60, -214, -457, -400, -36, 47, 8, -151, -489, -327, 85, -297, -395, -258, -31, -56, -500, -61, -18,
-474, -426, -162,
-79, 25, -361, -88, -241, -225, -367, -440, -200, 38, -248, -429, -284, -23, 19, -220, -105, -81, -269, -488,
-204, -28, -138,
39, -389, 40, -263, -297, -400, -158, -310, -270, -107, -336, -164, 36, 11, -192, -359, -136, -230, -410, -66,
67, -396, -146,
-158, -264, -13, -15, -425, 58, -25, -241, 85, -82, -49, -150, -37, -493, -284, -107, 93, -183, -60, -261,
-310, -380]
print find_maximum_subarray(ar, 0, len(ar) - 1)