Максимальная прибыль от одной продажи

Question

Предположим, нам дан массив из n целых чисел, представляющих цены акций за один день. Мы хотим найти пару (buyDay, sellDay) , с buyDay & le; sellDay , такой, что если бы мы купили акцию buyDay и продали ее sellDay , мы получили бы максимальную прибыль.

Очевидно, что существует O (n ² ) решение алгоритма, опробовав все возможные пары (buyDay, sellDay) и выбрав лучшее из из всех них. Однако есть ли лучший алгоритм, возможно, который работает за O (n) время?

Answer 1

Чистое решение:

+ (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;
}

Answer 2

Единственный ответ, который действительно отвечает на вопрос, - это ответ @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];
}

Answer 3

После провала экзамена по кодированию на должности инженера по решениям 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);

Answer 4

Для всех ответов, отслеживающих минимальные и максимальные элементы, это решение на самом деле является решением O (n ^ 2).Это связано с тем, что в конце необходимо проверить, наступил ли максимум после минимума или нет.Если это не так, дальнейшие итерации требуются до тех пор, пока это условие не будет выполнено, и это оставляет наихудший случай O (n ^ 2).И если вы хотите пропустить дополнительные итерации, тогда потребуется гораздо больше места.В любом случае, нет-нет по сравнению с решением динамического программирования

Answer 5

Это максимальная разница между двумя элементами в массиве, и это мое решение:

O (N) сложность времени O (1) сложность пространства

    int[] arr   =   {5, 4, 6 ,7 ,6 ,3 ,2, 5};

    int start   =   0;
    int end     =   0;
    int max     =   0;
    for(int i=1; i<arr.length; i++){
        int currMax =   arr[i] - arr[i-1];
        if(currMax>0){
            if((arr[i] -arr[start])>=currMax && ((arr[i] -arr[start])>=(arr[end] -arr[start]))){

                 end    =   i;
            }
            else if(currMax>(arr[i] -arr[start]) && currMax >(arr[end] - arr[start])){
                start   =   i-1;
                end =   i;
            }
        }
    }
    max =   arr[end] - arr[start];
    System.out.println("max: "+max+" start: "+start+" end: "+end);

Answer 6

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

Например,давайте определим min_arr и max_arr, с заданным массивом arr.Индекс i в min_arr будет минимальным элементом в arr для всех индексов <= 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) время, но я считаю, что оно занимает много места.

Answer 7

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");
}

Answer 8

def get_max_profit(stock):
    p=stock[0]
    max_profit=0
    maxp=p
    minp=p
    for i in range(1,len(stock)):
        p=min(p,stock[i])
        profit=stock[i]-p
        if profit>max_profit:
            maxp=stock[i]
            minp=p
            max_profit=profit
    return minp,maxp,max_profit



stock_prices = [310,315,275,295,260,270,290,230,255,250]
print(get_max_profit(stock_prices))

Эта программа в python3 может возвращать цену покупки и цену продажи, которая максимизирует прибыль, вычисленную с помощью Временная сложность O (n) и Пространственная сложность O (1) .

Answer 9

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

public static int maxProfit(List<Integer> 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;
 }
}