FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Python/dynamic_programming/max_sub_array.py at master · singlav/Python · GitHub
singlav
Python
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Python
/
dynamic_programming
/
max_sub_array.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
93 lines (81 loc) · 2.57 KB
Breadcrumbs
Python
/
dynamic_programming
/
max_sub_array.py
Copy path
File metadata and controls
93 lines (81 loc) · 2.57 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
"""
author : Mayank Kumar Jha (mk9440)
"""
from
typing
import
List
def
find_max_sub_array
(
A
,
low
,
high
):
if
low
==
high
:
return
low
,
high
,
A
[
low
]
else
:
mid
=
(
low
+
high
)
//
2
left_low
,
left_high
,
left_sum
=
find_max_sub_array
(
A
,
low
,
mid
)
right_low
,
right_high
,
right_sum
=
find_max_sub_array
(
A
,
mid
+
1
,
high
)
cross_left
,
cross_right
,
cross_sum
=
find_max_cross_sum
(
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_left
,
cross_right
,
cross_sum
def
find_max_cross_sum
(
A
,
low
,
mid
,
high
):
left_sum
,
max_left
=
-
999999999
,
-
1
right_sum
,
max_right
=
-
999999999
,
-
1
summ
=
0
for
i
in
range
(
mid
,
low
-
1
,
-
1
):
summ
+=
A
[
i
]
if
summ
>
left_sum
:
left_sum
=
summ
max_left
=
i
summ
=
0
for
i
in
range
(
mid
+
1
,
high
+
1
):
summ
+=
A
[
i
]
if
summ
>
right_sum
:
right_sum
=
summ
max_right
=
i
return
max_left
,
max_right
, (
left_sum
+
right_sum
)
def
max_sub_array
(
nums
:
List
[
int
])
->
int
:
"""
Finds the contiguous subarray which has the largest sum and return its sum.
>>> max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])
6
An empty (sub)array has sum 0.
>>> max_sub_array([])
0
If all elements are negative, the largest subarray would be the empty array,
having the sum 0.
>>> max_sub_array([-1, -2, -3])
0
>>> max_sub_array([5, -2, -3])
5
>>> max_sub_array([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
187
"""
best
=
0
current
=
0
for
i
in
nums
:
current
+=
i
if
current
<
0
:
current
=
0
best
=
max
(
best
,
current
)
return
best
if
__name__
==
"__main__"
:
"""
A random simulation of this algorithm.
"""
import
time
import
matplotlib
.
pyplot
as
plt
from
random
import
randint
inputs
=
[
10
,
100
,
1000
,
10000
,
50000
,
100000
,
200000
,
300000
,
400000
,
500000
]
tim
=
[]
for
i
in
inputs
:
li
=
[
randint
(
1
,
i
)
for
j
in
range
(
i
)]
strt
=
time
.
time
()
(
find_max_sub_array
(
li
,
0
,
len
(
li
)
-
1
))
end
=
time
.
time
()
tim
.
append
(
end
-
strt
)
print
(
"No of Inputs Time Taken"
)
for
i
in
range
(
len
(
inputs
)):
print
(
inputs
[
i
],
"
\t
\t
"
,
tim
[
i
])
plt
.
plot
(
inputs
,
tim
)
plt
.
xlabel
(
"Number of Inputs"
)
plt
.
ylabel
(
"Time taken in seconds "
)
plt
.
show
()
Back
|
FazBrowse Home
|
New Git URL