Algorithms/maximum_subarray/Python/max_sub_array.py at master · NITSkmOS/Algorithms · GitHub

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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()
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
"""
Here Maximum SubArray problem has been implemented on the Share
Market Data Analysis. Where prices of every day has been given.
We have to find the buying and selling day so that the profit will
be maximum. Here the Divide and Conquer method is used and
time-complexity is O(nlogn).For more information visit-
<https://en.wikipedia.org/wiki/Maximum_subarray_problem>
"""


defmax_sub_array(arr, low, high):
"""
 Method to find maximum sub array.

 :param low: kjndn
 :param high: kjndknfg
 """
iflow==high:
# if there is only one day
returnlow, low+1, arr[low]

else:
mid=int((low+high) /2)
# ll, lh, ls are respectively left-low, left-high, left-sum
# rl, rh, rs are respectively right-low, right-high, right-sum
# cl, ch, cs are respectively cross-low, cross-high, cross-sum

ll, lh, ls=max_sub_array(arr, low, mid)
rl, rh, rs=max_sub_array(arr, mid+1, high)
cl, ch, cs=cross_sub_array(arr, low, mid, high)

max_sum=max(ls, rs, cs)

ifmax_sumisls:
returnll, lh, ls
elifmax_sumisrs:
returnrl, rh, rs
else:
returncl, ch, cs


defcross_sub_array(arr, low, mid, high):
"""
 :param mid: lsum is left sum
 """
lsum=-10000
sum=0
maxl=mid
maxr=mid+1
foriinrange(mid, low-1, -1):
sum=sum+arr[i]
ifsum>lsum:
lsum=sum
maxl=i

# rsum is right sum
rsum=-10000
sum=0
foriinrange(mid+1, high+1):
sum=sum+arr[i]
ifsum>rsum:
rsum=sum
maxr=i+1
returnmaxl, maxr, (lsum+rsum)


defmain():
# price is array of the prices where each index of array
# represents the day.
# price_difference is array of profit(either +ve or -ve)

price= [4, 9, 5, 13, 16, 7, 8]

iflen(price) <=1:
print('Same day purchase and sell.So no profit.')
return

price_difference= []
fordayinrange(1, len(price)):
price_difference.append(price[day] -price[day-1])

# l is day of purchasing
# h is day of selling
# s is profit

l, h, s=max_sub_array(price_difference, 0, (len(price_difference) -1))
ifs<0:
# if it happens that price drops and never rises to
# the price when it was purchased

print('No days found to get profit')
else:
# To be more real-life oriented we start counting from day-1 instead of
# day-0

print('Day of Purchase:', l+1,
'\nDay of Selling:', h+1,
'\nProfit:', s)


if__name__=='__main__':
main()