Алгоритм и структура данных для случая [дубликат]

Вот мое решение

public static int maxProfit (ArrayList in) {

    int min = in.get(0), max = 0;
    for(int i=0; i<in.size()-1;i++){

        min=Math.min(min, in.get(i));

        max = Math.max(in.get(i)- min, max);
    }

    return max;
}

}

Ответ на верхний голос не учитывает случаи, когда максимальная прибыль отрицательна и должна быть изменена, чтобы допускать такие случаи. Это можно сделать, ограничив диапазон цикла до (len (a) - 1) и изменив способ получения прибыли путем изменения индекса на единицу.

def singSellProfit(a):
profit = -max(a)
low = a[0]

for i in range(len(a) - 1):
    low = min(low, a[i])
    profit = max(profit, a[i + 1] - low)
return profit

Сравните эту версию функции с предыдущим для массива:

s = [19,11,10,8,5,2]

singSellProfit(s)
-1

DynamicProgrammingSingleSellProfit(s)
0

здесь мое решение Java:

public static void main(String[] args) {
    int A[] = {5,10,4,6,12};

    int min = A[0]; // Lets assume first element is minimum
    int maxProfit = 0; // 0 profit, if we buy & sell on same day.
    int profit = 0;
    int minIndex = 0; // Index of buy date
    int maxIndex = 0; // Index of sell date

    //Run the loop from next element
    for (int i = 1; i < A.length; i++) {
        //Keep track of minimum buy price & index
        if (A[i] < min) {
            min = A[i];
            minIndex = i;
        }
        profit = A[i] - min;
        //If new profit is more than previous profit, keep it and update the max index
        if (profit > maxProfit) {
            maxProfit = profit;
            maxIndex = i;
        }
    }
    System.out.println("maxProfit is "+maxProfit);
    System.out.println("minIndex is "+minIndex);
    System.out.println("maxIndex is "+maxIndex);     
}

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

Например , давайте определим min_arr и max_arr, причем данный массив будет arr. Индекс i в min_arr будет минимальным элементом в arr для всех индексов <= i (слева от i и включает i). Индекс i в max_arr будет максимальным элементом в arr для всех индексов >= i (справа и в том числе i). Затем вы можете найти максимальную разницу между соответствующими элементами в max_arr и `min_arr ':

def max_profit(arr)
   min_arr = []
   min_el = arr.first
   arr.each do |el|
       if el < min_el
           min_el = el
           min_arr << min_el
       else
           min_arr << min_el
       end
   end

   max_arr = []
   max_el = arr.last
   arr.reverse.each do |el|
       if el > max_el
           max_el = el
           max_arr.unshift(max_el)
       else
           max_arr.unshift(max_el)
       end

   end

   max_difference = max_arr.first - min_arr.first
   1.upto(arr.length-1) do |i|
        max_difference = max_arr[i] - min_arr[i] if max_difference < max_arr[i] - min_arr[i]  
   end

   return max_difference 
end

Это должно выполняться в O (n) времени, но я считаю, что он использует много пространство.

После того, как это произошло в текущем экзамене по кодированию для инженера-конструктора FB, мне пришлось решить его в спокойной прохладной атмосфере, так что вот мои 2 цента:

var max_profit = 0;
var stockPrices = [23,40,21,67,1,50,22,38,2,62];

var currentBestBuy = 0; 
var currentBestSell = 0;
var min = 0;

for(var i = 0;i < (stockPrices.length - 1) ; i++){
    if(( stockPrices[i + 1] - stockPrices[currentBestBuy] > max_profit) ){
        max_profit = stockPrices[i + 1] - stockPrices[currentBestBuy];
        currentBestSell = i + 1;  
    }
    if(stockPrices[i] < stockPrices[currentBestBuy]){
            min = i;
        }
    if( max_profit < stockPrices[i + 1] - stockPrices[min] ){
        max_profit = stockPrices[i + 1] - stockPrices[min];
        currentBestSell = i + 1;
        currentBestBuy = min;
    }
}

console.log(currentBestBuy);
console.log(currentBestSell);
console.log(max_profit);

static void findmaxprofit(int[] stockvalues){
    int buy=0,sell=0,buyingpoint=0,sellingpoint=0,profit=0,currentprofit=0;
    int finalbuy=0,finalsell=0;
    if(stockvalues.length!=0){
        buy=stockvalues[0];
    }           
    for(int i=1;i<stockvalues.length;i++){  
        if(stockvalues[i]<buy&&i!=stockvalues.length-1){                
            buy=stockvalues[i];
            buyingpoint=i;
        }               
        else if(stockvalues[i]>buy){                
            sell=stockvalues[i];
            sellingpoint=i;
        }
        currentprofit=sell-buy;         
        if(profit<currentprofit&&sellingpoint>buyingpoint){             
            finalbuy=buy;
            finalsell=sell;
            profit=currentprofit;
        }

    }
    if(profit>0)
    System.out.println("Buy shares at "+finalbuy+" INR and Sell Shares "+finalsell+" INR and Profit of "+profit+" INR");
    else
        System.out.println("Don't do Share transacations today");
}

Единственный ответ, действительно отвечающий на вопрос, - это вопрос @akash_magoon (и таким простым способом!), но он не возвращает точный объект, указанный в вопросе. Я немного реорганизовал и получил ответ в PHP, возвращающий только то, что задано:

function maximizeProfit(array $dailyPrices)
{
    $buyDay = $sellDay = $cheaperDay = $profit = 0;

    for ($today = 0; $today < count($dailyPrices); $today++) {
        if ($dailyPrices[$today] < $dailyPrices[$cheaperDay]) {
            $cheaperDay = $today;
        } elseif ($dailyPrices[$today] - $dailyPrices[$cheaperDay] > $profit) {
            $buyDay  = $cheaperDay;
            $sellDay = $today;
            $profit   = $dailyPrices[$today] - $dailyPrices[$cheaperDay];
        }
    }
    return [$buyDay, $sellDay];
}

Оптимальное решение:

+ (int)maxProfit:(NSArray *)prices {
    int maxProfit = 0;

    int bestBuy = 0;
    int bestSell = 0;
    int currentBestBuy = 0;

    for (int i= 1; i < prices.count; i++) {
        int todayPrice = [prices[i] intValue];
        int bestBuyPrice = [prices[currentBestBuy] intValue];
        if (todayPrice < bestBuyPrice) {
            currentBestBuy = i;
            bestBuyPrice = todayPrice;
        }

        if (maxProfit < (todayPrice - bestBuyPrice)) {
            bestSell = i;
            bestBuy = currentBestBuy;
            maxProfit = (todayPrice - bestBuyPrice);
        }
    }

    NSLog(@"Buy Day : %d", bestBuy);
    NSLog(@"Sell Day : %d", bestSell);

    return maxProfit;
}

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

Как уже отмечалось, его можно решить грубо -force в O (N ^ 2) времени. Для каждой записи в массиве (или списке), итерации по всем предыдущим записям, чтобы получить min или max в зависимости от того, найти ли проблему наибольший коэффициент усиления или потери.

Вот как думать о решении в O (N): каждая запись представляет собой новый возможный максимум (или мин). Затем все, что нам нужно сделать, это сохранить предыдущий мин (или максимум) и сравнить diff с током и предыдущим мин (или max). Легкий peasy.

Вот код, в Java как тест JUnit:

import org.junit.Test;

public class MaxDiffOverSeriesProblem {

    @Test
    public void test1() {
        int[] testArr = new int[]{100, 80, 70, 65, 95, 120, 150, 75, 95, 100, 110, 120, 90, 80, 85, 90};

        System.out.println("maxLoss: " + calculateMaxLossOverSeries(testArr) + ", maxGain: " + calculateMaxGainOverSeries(testArr));
    }

    private int calculateMaxLossOverSeries(int[] arr) {
        int maxLoss = 0;

        int idxMax = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[idxMax]) {
                idxMax = i;
            }

            if (arr[idxMax] - arr[i] > maxLoss) {
                maxLoss = arr[idxMax] - arr[i];
            }           
        }

        return maxLoss;
    }

    private int calculateMaxGainOverSeries(int[] arr) {
        int maxGain = 0;

        int idxMin = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < arr[idxMin]) {
                idxMin = i;
            }

            if (arr[i] - arr[idxMin] > maxGain) {
                maxGain = arr[i] - arr[idxMin];
            }           
        }

        return maxGain;
    }

}

В случае вычисления наибольшей потери мы отслеживаем максимальное количество в списке (цена покупки) до текущей записи. Затем мы вычисляем разницу между максимальным и текущим. Если max - current> maxLoss, то мы сохраняем этот diff как новый maxLoss. Так как индекс max гарантированно меньше индекса тока, мы гарантируем, что дата «buy» меньше даты «sell».

В случае вычисления наибольшего выигрыша все обращается вспять. Мы отслеживаем мин в списке до текущей записи. Мы вычисляем разность между минимумом и током (изменяем порядок в вычитании). Если current - min> maxGain, то мы сохраняем этот diff как новый maxGain. Опять же, индекс «buy» (min) приходит перед индексом текущего («продавать»).

Нам остается только отслеживать maxGain (или maxLoss), а индекс min или макс, но не оба, и нам не нужно сравнивать индексы, чтобы подтвердить, что «покупка» меньше, чем «продать», поскольку мы получаем это естественно.

Я придумал простое решение - код более понятен. Это один из вопросов динамического программирования.

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

namespace MaxProfitForSharePrice
{
    class MaxProfitForSharePrice
    {
        private static int findMax(int a, int b)
        {
            return a > b ? a : b;
        }

        private static void GetMaxProfit(int[] sharePrices)
        {
            int minSharePrice = sharePrices[0], maxSharePrice = 0, MaxProft = 0;
            int shareBuyValue = sharePrices[0], shareSellValue = sharePrices[0];

            for (int i = 0; i < sharePrices.Length; i++)
            {
                if (sharePrices[i] < minSharePrice )
                {
                    minSharePrice = sharePrices[i];
                    // if we update the min value of share, we need to reset the Max value as 
                    // we can only do this transaction in-sequence. We need to buy first and then only we can sell.
                    maxSharePrice = 0; 
                }
                else 
                {
                    maxSharePrice = sharePrices[i];
                }

                // We are checking if max and min share value of stock are going to
                // give us better profit compare to the previously stored one, then store those share values.
                if (MaxProft < (maxSharePrice - minSharePrice))
                {
                    shareBuyValue = minSharePrice;
                    shareSellValue = maxSharePrice;
                }

                MaxProft = findMax(MaxProft, maxSharePrice - minSharePrice);
            }

            Console.WriteLine("Buy stock at ${0} and sell at ${1}, maximum profit can be earned ${2}.", shareBuyValue, shareSellValue, MaxProft);
        }

        static void Main(string[] args)
        {
           int[] sampleArray = new int[] { 1, 3, 4, 1, 1, 2, 11 };
           GetMaxProfit(sampleArray);
            Console.ReadLine();
        }
    }
}

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

    int prices[] = { 38, 37, 35, 31, 20, 24, 35, 21, 24, 21, 23, 20, 23, 25, 27 };

    int buyDate = 0, tempbuyDate = 0;
    int sellDate = 0, tempsellDate = 0; 

    int profit = 0, tempProfit =0;
    int i ,x = prices.length;
    int previousDayPrice = prices[0], currentDayprice=0;

    for(i=1 ; i<x; i++ ) {

        currentDayprice = prices[i];

        if(currentDayprice > previousDayPrice ) {  // price went up

            tempProfit = tempProfit + currentDayprice - previousDayPrice;
            tempsellDate = i;
        }
        else { // price went down 

            if(tempProfit>profit) { // check if the current Profit is higher than previous profit....

                profit = tempProfit;
                sellDate = tempsellDate;
                buyDate = tempbuyDate;
            } 
                                     // re-intialized buy&sell date, profit....
                tempsellDate = i;
                tempbuyDate = i;
                tempProfit =0;
        }
        previousDayPrice = currentDayprice;
    }

    // if the profit is highest till the last date....
    if(tempProfit>profit) {
        System.out.println("buydate " + tempbuyDate + " selldate " + tempsellDate + " profit " + tempProfit );
    }
    else {
        System.out.println("buydate " + buyDate + " selldate " + sellDate + " profit " + profit );
    }