Максимизация прибыли для данных котировок акций

Ответ 1

Я согласен с логикой вашего метода, но нет необходимости выполнять рекурсивную обработку или глобальные поиски максимумов. Чтобы найти дни продажи/покупки, вам просто нужно посмотреть каждый день:

Трюк заключается в том, чтобы начать с конца. Торговля запасами легко, если ваше путешествие назад вовремя!

Если вы считаете, что код легче читать, чем слова, просто пропустите мое объяснение, но здесь идет:

Чтение с конца, посмотрите на цену того дня. Это самая высокая цена на данный момент (с конца), а затем продайте! В последний день (где мы начинаем читать) вы всегда будете продавать.

Затем перейдите на следующий день (помните, назад вовремя). Это самая высокая цена на данный момент (из всего, на что мы смотрели)? - Тогда продайте все, вы не найдете лучшего дня. Иначе цены растут, поэтому покупайте. продолжайте то же самое до начала.

Вся проблема решена с помощью одного единственного обратного цикла: вычисление как решений, так и прибыли торговли.

Здесь код в C-like python: (я избегал большинства питонических вещей. Должен быть читаемым для человека C)

def calcprofit(stockvalues): 
    dobuy=[1]*len(stockvalues) # 1 for buy, 0 for sell
    prof=0
    m=0
    for i in reversed(range(len(stockvalues))):
        ai=stockvalues[i] # shorthand name
        if m<=ai:
            dobuy[i]=0
            m=ai
        prof+=m-ai
    return (prof,dobuy)  

Примеры:

calcprofit([1,3,1,2]) gives (3, [1, 0, 1, 0])
calcprofit([1,2,100]) gives (197, [1, 1, 0])
calcprofit([5,3,2])   gives (0, [0, 0, 0])
calcprofit([31,312,3,35,33,3,44,123,126,2,4,1]) gives
 (798, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0])

Обратите внимание, что m - самая высокая цена акций, которую мы видели (с конца). Если ai==m, то прибыль от акций, купленных на этапе, равна 0: после этого мы снизили или стабилизировали цену и не купили.

Вы можете проверить правильность расчета прибыли с помощью простой петли (для простоты представьте себе ее в рамках указанной выше функции)

stock=0
money=0
for i in range(len(stockvalues)):  
    if dobuy[i]:
        stock+=1
        money-=stockvalues[i]
    else:
        money+=stockvalues[i]*stock
        stock=0
print("profit was: ",money)

Ответ 2

Еще один способ взглянуть на это:
В предварительной обработке для каждого элемента a[i] найдите a[j] s.t. j > i и максимизирует (a[j] - a[i])
поэтому Лучший, который вы можете сделать по цене a[i], покупается по цене a[i] и продается по цене a[j]. Если не существует a[j] s.t. a[j] > a[i], тогда a[i] не является точкой покупки.

Время предварительной обработки: O(N)

S[N-1] = A[N-1];
for(int i=N-2; i>=0; --i)
       S[i] = max(A[i], S[i+1]);

Здесь S [i] - цена, по которой вы должны продать [i].

Суммирование общей прибыли: O(N)

long long int Profit = 0;
    for(int i=0;i<N;++i)
          Profit += max(0,  (S[i]-A[i]) );

Ответ 3

Другое решение O (n) для этой задачи может быть выполнено путем использования локального минимума и максимума, нахо- дящего наилучшее почтение (прибыль) между макс и мин, зная, что max должен иметь больший индекс, а затем min. Нам также нужно посмотреть предыдущий лучший локальный минимум (реализация С#).

public int[] GetBestShareBuyingStrategy(int[] price)
    {
        var n = price.Length;
        if (n <= 1)
            return null;

        var profit = 0;
        var min = 0;
        var max = 0;
        var lmin = 0;

        for (var i = 1; i < n; i++)
        {
            var lmax = i;
            var lp = price[lmax] - price[lmin];
            if (lp <= 0)
            {
                lmin = i;
            }
            else
            {
                var tp = price[lmax] - price[min];
                if (lp > tp && lp > profit)
                {
                    min = lmin;
                    max = lmax;
                    profit = lp;
                }
                else if (tp > profit)
                {
                    max = lmax;
                    profit = tp;
                }
            }
        }

        return profit > 0
            ? new [] {min, max}
            : null;
    }



    [Test]
    [TestCase(new[] { 10, 9, 8, 7, 3 })]
    [TestCase(new[] { 5, 5, 5, 5, 5 })]
    [TestCase(new[] { 5, 4, 4, 4 })]
    [TestCase(new[] { 5, 5, 3, 3 })]
    public void GetBestShareBuyingStrategy_When_no_sense_to_buy(int[] sharePrices)
    {
        var resultStrategy = GetBestShareBuyingStrategy(sharePrices);
        Assert.IsNull(resultStrategy);
    }

    [Test]
    [TestCase(new[] { 10, 8, 12, 20, 10 }, 1, 3)]
    [TestCase(new[] { 5, 8, 12, 20, 30 }, 0, 4)]
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)]
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)]
    [TestCase(new[] { 10, 2, 8, 1, 15, 20, 10, 22 }, 3, 7)]
    [TestCase(new[] { 1, 5, 2, 7, 3, 9, 8, 7 }, 0, 5)]
    [TestCase(new[] { 3, 5, 2, 7, 3, 9, 8, 7 }, 2, 5)]
    public void GetBestShareBuyingStrategy_PositiveStrategy(int[] sharePrices, int buyOn, int sellOn)
    {
        var resultStrategy = GetBestShareBuyingStrategy(sharePrices);
        Assert.AreEqual(buyOn, resultStrategy[0]);
        Assert.AreEqual(sellOn, resultStrategy[1]);
    }

Ответ 4

Я просто решил эту проблему на сайте конкурса. Я думаю, что я получил более простой алгоритм, чем принятый ответ.

1. smax = maximum stock price from the list
2. then find the profit by assuming you have bought all the stocks till smax 
   and you sell it at the price of smax
3. then check if smax is the last element of the stock price list 
   if yes then return profit as answer, 
   if no 
   then make a new list containing stock prices after smax to the last stock price
   and repeat steps 1-3 and keep adding profit of each iteration to get the final profit.

Ответ 5

0. Начните с конца массива, чтобы не нужно было рекурсивно 1. smax = максимальная цена акций из списка
2. Затем найдите прибыль, предположив, что вы купили все акции до smax  и вы продаете его по цене smax

          public static void main(String[] args) {

          Scanner sc = new Scanner(System.in);
          int numOfTestCase = sc.nextInt();
          for (int i = 0; i < numOfTestCase; i++) {
                 int n = sc.nextInt();
                 long profit = 0;
                 int[] stockPrice = new int[n];

                 for (int j = 0; j < n; j++) {
                       stockPrice[j] = sc.nextInt();
                 }

                 int currMax = Integer.MIN_VALUE;

                 for (int j = n - 1; j >= 0; j--) {
                       if (currMax < stockPrice[j]) {
                              currMax = stockPrice[j];
                       }
                       profit += (currMax - stockPrice[j]);
                 }
                 System.out.println(profit);


          }
   }

Ответ 6

Ваша логика правильная...

продавать на глобальных максимумах.. но рекурсия не требуется...

если i-й элемент является глобальным максимумом... продайте все запасы до i!

Теперь проблема сводится к предыдущему ответу + я + 1 в N...

рекурсия не требуется... линейно мы можем вычислить!

Ответ 7

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

function profit(prices){
    var totalStocks = 0, profitMade = 0;

    var buySell = function(sortedPrices){
        for(var i = 0, len = sortedPrices.length; i < len; i++){
            if (i < len - 1){
                totalStocks++;
                profitMade = profitMade - sortedPrices[i];
            }else{
                profitMade = profitMade + totalStocks * sortedPrices[i];
                totalStocks = 0;
            }
        }
    }, splitMaxPrice = function(rawPrices){
        var leftStocks = rawPrices.splice(rawPrices.lastIndexOf(Math.max.apply(null, rawPrices))+1);
        buySell(rawPrices);
        if(leftStocks.length > 0){
            splitMaxPrice(leftStocks);
        }
        return;
    };

    splitMaxPrice(prices);

    return profitMade;

}