Помогите с задачей по программированию

Долго рассказывать, проще программу написать:

 from bisect import insort



input() # Количество не нужно

quotes = [int(s) for s in input().split()]



# Собираем все целесообразные пары сделок: индексы начальный и за концом.

# Начало - элемент [0] или меньший предыдущего.

# Конец - элемент последний или больший следующего.

# Это - линейный алгоритм.

# Сразу собираем и все объединения последовательностей.

# Это - уже линейно-логарифмический алгоритм.

# Поддерживаем порядок по убыванию прибыльности.



def profit(t): return quotes[t[1] - 1] / quotes[t[0]]



def negprofit(t): return -profit(t)



def update(ints, start, end):

    if end  1]:

        insort(ints, (s, end), key = negprofit)

    insort(ints, (start, end), key = negprofit)



def alltrades():

    start = 0

    intervals = []

    for i in range(1, len(quotes)):

        if quotes[i - 1] >= quotes[i]:

            update(intervals, start, i)

            start = i;

    update(intervals, start, len(quotes))

    return intervals



# Собираем последовательности непересекающихся сделок и выбираем наилучшую по прибыльности



def besttrades(ints, maxc):

    if not ints or not maxc: return ([], 1)

    bestt, bestp = [], 0

    for j in range(len(ints)):

        p = profit(ints[j])

        if p ** maxc = end or e  bestp: bestt, bestp = [ints[j]] + td, pc

    return (bestt, bestp)



bt, _ = besttrades(alltrades(), 2)

print(len(bt), *(f"{s+1} {e}" for s, e in sorted(bt)), sep = '\n') 

Кратко опишу суть.
Алгоритм имеет экспоненциальную сложность от количества возрастающих непрерывных последовательностей цен и от ограничения на количество сделок и будет работать с приемлемой скоростью только на выборках данных с небольшим количеством таких последовательностей или низким лимитом на количество сделок. К счастью, тут надо выбрать всего две пары сделок.

Основная проблема, из-за которой здесь неприменимы быстрые алгоритмы вроде Кадане - это необходимость учитывать все объединения последовательностей. Например, если у нас есть котировки "1 2 3 4 5 4 8", то придётся учесть раздельно "1 2 3 4 5" с пятикратной прибылью, "4 8" с двукратной прибылью и их объединение с восьмикратной прибылью. Естественно, 5 × 2 выгоднее, чем 8, но у нас - ограничение на количество сделок, а 8 выгоднее, чем 5 и 2 по отдельности.

Логика достаточно очевидна из кода. За линейно-логарифмическое время собираем все возможные пары сделок, включая объединения интервалов, в отсортированный по убыванию прибыльности список (фактически оно может оказаться квадратично-логарифмическим из-за вставки в середину, но это - не главная проблема).

Считаем прибыль разных комбинаций пар сделок, начиная с самых прибыльных. Берём верхушку, исключаем пары сделок в пересекающиеся с ней дни, и по оставшемуся списку рекурсивно подбираем наиболее прибыльный остаток. Потом берём следующий элемент после верхушки, снова считаем прибыль на оставшемся списке. Поскольку до текущего элемента все комбинации пройдены, смотрим только в остатке списка после него. Перебор останавливается либо по исчерпанию элементов, либо по достижении слишком низкого уровня прибыльности текущей пары сделок (список упорядочен). К сожалению, данная оптимизация не выводит алгоритм из экспоненциального класса, но кэширование найденных комбинаций по остаткам может это сделать. Возвращаем наиболее прибыльную комбинацию пар.

И в конце выводим лучшую комбинацию в хронологическом порядке.

 for s in [s for s, _ in ints if profit((s, end)) > 1]: 

 for s in {s for s, _ in ints if profit((s, end)) > 1}: