Вычислить оптимальные по доходу дни для сделок по покупке акций (Python)

Question

Помогите, пожалуйста, понять алгоритм написания кода, который бы искал не более 4 пар сделок купли продажи таким образом, чтобы получилась максимальная выгода. Никак не мог понять, как расписать алгоритм. Максимум, до чего додумался - это нарезать список цен в разные дни на подсписки так, чтобы начало следующего подспика был меньше конца предыдущего, то есть разбить на последовтельные подсписки. Вот условие и мой код

N = int(input())
prices = [int(i) for i in input().split()]
dprices = dict(zip(range(1, N + 1), prices))
a = []
s = []
i = prices.index(min(prices))
while i != len(prices) - 1:
    s.append(prices[i])
    if prices[i] > prices[i+1] or i == len(prices)-2:
        a.append(s)
        s = []
    i += 1
a[-1].append(prices[-1])
print(a)
day1 = []
day2 = []
for i in range(len(a)):
    for key, value in dprices.items():
        if a[i][0] == value:
            day1.append(key)
        if a[i][-1] == value:
            day2.append(key)

days = tuple(zip(day1, day2))
print(len(days))
for item in days:
    print(*item)

Answer 1

Реализуем то, что я написал в дубликате

Пройдите по массиву с конца, поддерживая текущий максимум (индекс imax) от k+1-го элемента до конца массива, и вычисляя наилучшую разность p[imax]-p[k], обновляйте максимум текущей выгоды, и записывайте эти значения во вспомогательный массив V. Таким образом, V[k] будет описывать лучшее вложение начиная с k-го элемента до конца.

Теперь пройдите от начала, поддерживая текущий минимум (индекс imin) от начала массива до j-1 элемента, вычисляя наилучшую разность p[j]-p[imin] c учётом вложения одного рубля, поддерживая максимум лучшего вложения Best от начала до k-го элемента, и комбинируйте текущий максимум с V[k+1], запоминайте лучшее значение Best*V[k+1]

Алгоритм линейный

Для лучшего понимания я сделал массив e для прибылей по первой сделке (в реальности хранить его не требуется) и вывод массивов.

Доработку для получения самих дней сделок оставил вопрошающему. Также следует обработать случай только одной сделки

pr = [int(i) for i in '2 1 4 3 2 3 8 6 1 3 6'.split()]
n = len(pr)
v = [0]*n
e = [0]*n
print(pr)

imax = n-1
bestdiff = 0
for k in reversed(range(n)):
    bestdiff = max(pr[imax] - pr[k], bestdiff)
    v[k] = bestdiff
    if pr[k] > pr[imax]:
        imax = k
print(v)

imin = 0
bestdiff = 0
maxprofit = 0
for k in range(n-2):
    bestdiff = max(pr[k] - pr[imin], bestdiff)
    e[k] = bestdiff
    profit = bestdiff * v[k+1]
    maxprofit = max(profit, maxprofit)
    if pr[k] < pr[imin]:
        imin = k

print(e)

print(maxprofit)

Результат:

    b              s     b     s    дни сделок        
[2, 1, 4, 3, 2, 3, 8, 6, 1, 3, 6]   цены
[7, 7, 6, 6, 6, 5, 5, 5, 5, 3, 0]   вторая купля-продажа
[0, 0, 3, 3, 3, 3, 7, 7, 7, 0, 0]   первая купля-продажа
35                                  сумма у Кузи

Answer 2

n = int(input())
pr = list(map(int, input().split()))
v = [0]*n
e = [0]*n
sum_v_e = [0]*n
imax = n-1
bestdiff = 0

for k in reversed(range(n)):
    bestdiff = max(pr[imax] - pr[k], bestdiff)
    v[k] = bestdiff
    if pr[k] > pr[imax]:
        imax = k

imin = 0
bestdiff = 0

for k in range(n - 2):
    bestdiff = max(pr[k] - pr[imin], bestdiff)
    e[k] = bestdiff
    sum_v_e[k] = e[k] + v[k]

    if pr[k] < pr[imin]:
        imin = k

sum_all_element_v = sum(v)
sum_all_element_e = sum(e)


if sum_all_element_v == 0 and sum_all_element_e == 0:
    print(0)
elif sum_all_element_e == 0 or max(v) == max(sum_v_e):
    print(1)

    max_value = max(v)
    indices_max_v = [index for index, val in enumerate(v) if val == max_value]
    min_value = min(v)
    indices_min_v = v.index(min_value)
    print(indices_max_v[-1] + 1, indices_min_v + 1)
else:
    print(2)

    min_value = min(e)
    max_value = max(sum_v_e)
    indices_min_e = [index for index, val in enumerate(e[:sum_v_e.index(max_value) + 1]) if val == min_value]
    indices_max_e = sum_v_e.index(max_value) + 1
    print(indices_min_e[-1] + 1, indices_max_e)

    max_value = max(v[indices_max_e:])
    indices_max_v = [index for index, val in enumerate(v) if val == max_value]
    min_value = min(v)
    indices_min_v = v.index(min_value)
    print(indices_max_v[-1] + 1, indices_min_v + 1)

print(v)
print(e)
print(sum_v_e)

Answer 3

Не уверен на 100% но исправленное решение

n = int(input())
pr = [int(x) for x in input().split(" ")]


r = [[0,[0,0]] for x in range(n)]
l = [[0,[0,0]] for x in range(n)]
print(pr)

imax = n-1
bestdiff = 0
best_b = n-1
best_s = n-1
for k in reversed(range(n)):
    if bestdiff < pr[imax] - pr[k]:
        bestdiff = pr[imax] - pr[k]
        best_b = k
        best_s = imax

    r[k][0] = bestdiff
    r[k][1]= [best_b, best_s]

    if pr[k] > pr[imax]:
        imax = k

print(r)

imin = 0
bestdiff = 0
best_b = 0
best_s = 0
for k in range(n):

    if bestdiff < pr[k] - pr[imin]:
        bestdiff = pr[k] - pr[imin]
        best_b = imin
        best_s = k

    l[k][0] = bestdiff
    l[k][1] = [best_b, best_s]

    if pr[k] < pr[imin]:
        imin = k

print(l)


r.sort(key=lambda x: x[0], reverse=True)
l.sort(key=lambda x: x[0], reverse=True)

max_profit = 0
deals = []

if len(l) >= len(r):
    base = l
    h = r
else:
    base = r
    h = l


for i in range(len(base)):
    for k in range(len(h)):

        if base[i][1][1] >= h[k][1][0] or base[i][1][0] >= h[k][1][1]:

            if max_profit < base[i][0] and base[i][0] >=  h[k][0]:
                max_profit = base[i][0] + 1
                deals = [base[i][1]]

            elif max_profit <  h[k][0] and  h[k][0] > base[i][0]:
                max_profit =  h[k][0] + 1
                deals = [h[k][1]]

        elif max_profit < base[i][0] *  h[k][0]:
            max_profit = base[i][0] *  h[k][0] + 1
            deals = [base[i][1],  h[k][1]]

print(len(deals))


for i in deals:
    print(f"{i[0]+1} {i[1]+1}")

БЛОГ НА HUSL

Вычислить оптимальные по доходу дни для сделок по покупке акций (Python)

Ответы (3 шт):