问题:求股票最大收益,股票每天的价格:[100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97] 买进和卖出都在当天结束后进行,在某一个时刻买入,并在某一个日期卖出。
"""
问题:求股票最大收益,股票每天的价格:[100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
买进和卖出都在当天结束后进行,在某一个时刻买入,并在某一个日期卖出
最大子数组问题求解
方法一: 直接双层遍历,查找每股差价最大的俩天
方法二: 分治策略,求连续最大的子数组问题(数组为差价的数组,每一项为当前天的价格减去上一天的价格)
找到数组的中间位置,然后考虑求解俩个子数组,那么数组的最大子数组,分为三种情况:
1、完全位于子数组A[low, mid]中,因此 low <= i <= j <= mid
2、完全位于子数组A[mid+1, high]中,因此 mid < i <= j <= high
3、跨越了中点,因此 low <= i < mid <= j <= high
"""
def traverse_all_possible(array_list: list):
"""
暴力求解的方式,遍历所有的元素的差值
:param array_list:
:return:
"""
max_income, start, end = 0, 0, 0
for start_num, i in enumerate(array_list):
for end_num, j in enumerate(array_list[start_num:]):
if j - i > max_income:
max_income = j - i
start = start_num
end = end_num + start_num
return max_income, start, end
def find_max_crossing_subarray(array_list: list, low: int, mid: int, high: int):
"""
查找最大交叉子数组
:param array_list:
:param low:
:param mid:
:param high:
:return:
"""
left_sum, left_max, left_num = float("-inf"), 0, 0
for i in range(mid, low - 1, -1):
left_max = left_max + array_list[i]
if left_max > left_sum:
left_sum = left_max
left_num = i
right_sum, right_max, right_num = float("-inf"), 0, len(array_list) - 1
for j in range(mid + 1, high + 1):
right_max = right_max + array_list[j]
if right_max > right_sum:
right_sum = right_max
right_num = j
return left_num, right_num, left_sum + right_sum
def find_maximum_subarray(array_list: list, low: int, high: int):
"""
分治策略具体求解当前最大子数组问题
:param array_list:
:param low:
:param high:
:return:
"""
if low == high:
return low, high, array_list[low]
else:
mid = int((low + high) / 2)
left_low, left_high, left_sum = find_maximum_subarray(array_list, low, mid)
right_low, right_high, right_sum = find_maximum_subarray(array_list, mid + 1, high)
cross_low, cross_high, cross_sum = find_max_crossing_subarray(array_list, 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__":
test_list_01 = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
print(traverse_all_possible(test_list_01))
test_list_02 = [0, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print(find_maximum_subarray(test_list_02, 0, len(test_list_02) - 1))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)