Как я могу улучшить временную сложность этого алгоритма для определения максимальной цены акций?

Question

Я в настоящее время сдаю тестовые испытания и 2 из 10 других случаев, поэтому 4 из 12. Однако я не могу пройти через все данные.Я получаю прекращение из-за ошибки тайм-аута, что означает, что мое решение недостаточно быстрое.

def stockmax(prices):
    total = 0 
    for index, price in enumerate(prices):
        if index < len(prices) - 1: 
            section = max(prices[index+1:])

            if prices[index] < section:
                total += section - prices[index]
    return total

Я пытался сделать все за один цикл.Но как именно может ускорить этот тип вопроса.Я также попытался сократить некоторые строки кода, но он также неэффективен.

def stockmax(prices):
    total = 0 
    for index, price in enumerate(prices):
        if index < len(prices) - 1 and prices[index] < max(prices[index+1:]): 
              total += max(prices[index+1:]) - prices[index]
    return total

Хотя он проходит столько же тестов.Я также пытался использовать heapq, но он проходит те же тесты и терпит неудачу из-за времени.

def stockmax(prices):
    total = 0 
    for index, price in enumerate(prices):
        if index < len(prices) - 1:
            section = heapq.nlargest(1,prices[index+1:])[0]
            if prices[index] < section: 
                total += section - prices[index]
    return total

---

https://www.hackerrank.com/challenges/stockmax/topics/dynamic-programming-basics для получения подробной информации о проблеме.
https://hr -testcases-us-east-1.s3.amazonaws.com / 330 /input09.txt? AWSAccessKeyId = AKIAJ4WZFDFQTZRGO3QA & Expires = 1538902058 & Signature = 3% 2FnfZzPO8XKRNyGG0Yu9qJIptgk% 3D & response-content-type = text% 2Fplain 101 * * * 101 * * * * * * * * * * * * * * * * * из-за проблем, связанных с проверкой *1016* 1016 *1016* 101 * * * 101 * * * * * * * * * * * * * * из-за проблем, связанных с проверкой *1016* 1016 *1016* 101 * * * 101 * * * * * * * * *.

Ваши алгоритмы стали настолько хорошими в прогнозировании рынка, что теперь вы знаете, какой будет цена акции Wooden Orange Toothpicks Inc. (WOT) на следующие несколько дней.

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

Например, если вы знаете, что цены на следующие два дня равны prices = [1,2], вы должны купить одну акцию в первый день и продать ее в деньдва с прибылью, равной 1. Если вместо этого они равны prices = [2,1], прибыль не может быть получена, поэтому вы не покупаете или не продаете акции в эти дни.

Функция Описание

Завершите функцию stockmaxв редакторе ниже.Он должен возвращать целое число, представляющее максимальную достижимую прибыль.

stockmax имеет следующие параметры:

Цены: массив целых чисел, которые представляют прогнозируемые дневные цены на акции

Формат ввода

Первая строка содержит количество тестовых случаев t.

Каждая из следующих t пар строк содержит:

• В первой строке записано целое число n, количество прогнозируемых цен на WOT.
• Следующая строка содержит n разделенных пробелом целых чисел prices [i], каждое из которых является прогнозируемой ценой акции на день i.

Ограничения

1 <= t  <= 10
1 <= n <= 50000
1 <= prices [i] <= 100000

Выходные данныеФормат

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

Образец ввода

3
3
5 3 2
3
1 2 100
4
1 3 1 2

Образец вывода

0
197
3

Объяснение

В первом случае вы не можете получить какую-либо прибыль, потому что цена акции никогда не повышается.Во втором случае вы можете купить одну акцию в первые два дня и продать обе в третий день.В третьем случае вы можете купить одну акцию в день 1, продать одну в день 2, купить одну акцию в день 3 и продать одну акцию в день 4.

Answer 1

Если вы можете использовать Numpy, то что-то похожее на приведенное ниже должно быть довольно быстрым (я думаю, что это та же идея, что и ответ от @ גלעד ברקן).

import numpy as np

with open('.../input09.txt') as fd:
    numtests = int(fd.readline().strip())
    counter = 0
    numvals = 0
    vals = None
    steps = None
    for line in fd:
        if (counter % 2 == 0) :
            numvals = int(line.strip())
        else:
            vals = np.fromstring(line, dtype=int, sep=' ', count=numvals)
            assert len(vals) == numvals

            cum_max = np.maximum.accumulate(vals[::-1])
            np.roll(cum_max, -1)
            cum_max[len(cum_max) - 1] = 0
            delta = (cum_max - vals)
            print('#', counter + 1, 'sum:', np.sum(delta * (delta > 0)))

        counter += 1

оно запускается почти мгновенно на тестахот input09.txt.

Answer 2

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

Код Python:

def stockmax(prices):
  n = len(prices)
  highest = prices[n - 1]
  m = [0] * n

  # Travel back in time,
  # deciding whether to buy or not
  for i in xrange(n - 2, -1, -1):

    # The most profit buying stock at this point
    # is what we may have made the next day
    # (which is stored in m[i + 1])
    # and what we could make if we bought today
    m[i] = m[i + 1] + max(
      # buy
      highest - prices[i],
      # don't buy
      0
    )

    # Update the highest "future price"
    highest = max(highest, prices[i])

  return m[0]