-
Notifications
You must be signed in to change notification settings - Fork 0
/
subarrays.py
101 lines (96 loc) · 3.07 KB
/
subarrays.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
def max_subarray_sum(arr):
result = arr[0]
local_result = arr[0]
for i in range(1, len(arr)):
if local_result > 0:
local_result += arr[i]
else:
local_result = arr[i]
if local_result > result:
result = local_result
return result
def min_subarray_sum(arr):
result = arr[0]
local_result = arr[0]
for i in range(1, len(arr)):
if local_result < 0:
local_result += arr[i]
else:
local_result = arr[i]
if local_result < result:
result = local_result
return result
def max_subarray_prod(arr):
result = arr[0]
local_result_pos = arr[0]
local_result_neg = arr[0]
for i in range(1, len(arr)):
if local_result_pos * arr[i] > local_result_neg * arr[i]:
local_result_max = local_result_pos * arr[i]
local_result_min = local_result_neg * arr[i]
else:
local_result_max = local_result_neg * arr[i]
local_result_min = local_result_pos * arr[i]
if arr[i] > local_result_max:
local_result_pos = arr[i]
else:
local_result_pos = local_result_max
if arr[i] < local_result_min:
local_result_neg = arr[i]
else:
local_result_neg = local_result_min
if local_result_pos > result:
result = local_result_pos
return result
def min_subarray_prod(arr):
result = arr[0]
local_result_pos = arr[0]
local_result_neg = arr[0]
for i in range(1, len(arr)):
if local_result_pos * arr[i] > local_result_neg * arr[i]:
local_result_max = local_result_pos * arr[i]
local_result_min = local_result_neg * arr[i]
else:
local_result_max = local_result_neg * arr[i]
local_result_min = local_result_pos * arr[i]
if arr[i] > local_result_max:
local_result_pos = arr[i]
else:
local_result_pos = local_result_max
if arr[i] < local_result_min:
local_result_neg = arr[i]
else:
local_result_neg = local_result_min
if local_result_neg < result:
result = local_result_neg
return result
def max_circular_subarray_sum(arr):
max_elem = arr[0]
arr_sum = 0
for i in range(0, len(arr)):
if arr[i] > max_elem:
max_elem = arr[i]
arr_sum += arr[i]
if max_elem < 0:
return max_elem
max_simple_sum = max_subarray_sum(arr)
max_circle_sum = arr_sum - min_subarray_sum(arr)
if max_simple_sum > max_circle_sum:
return max_simple_sum
else:
return max_circle_sum
def min_circular_subarray_sum(arr):
min_elem = arr[0]
arr_sum = 0
for i in range(0, len(arr)):
if arr[i] < min_elem:
min_elem = arr[i]
arr_sum += arr[i]
if min_elem > 0:
return min_elem
min_simple_sum = min_subarray_sum(arr)
min_circle_sum = arr_sum - max_subarray_sum(arr)
if min_simple_sum < min_circle_sum:
return min_simple_sum
else:
return min_circle_sum