Didžiausias pelnas iš vieno pardavimo

Tarkime, mes suteikiame n sveikų skaičių masyvą, kuris parodo akcijų kainas per vieną dieną. Norime rasti porą (buyDay, sellDay) su buyDay le; tad, jei mes nupirksime akcijas buyDay ir pardavėme jas parduoti, mes maksimaliai padidinsime savo pelną.

Akivaizdu, kad algoritmas turi tirpalą O (n 2 ), išbandęs visas galimas pirkimo dienas, parduoti dienas poras ir jas naudodamas kiek įmanoma. Tačiau ar yra geresnis algoritmas, galbūt tas, kuris veikia O (n) laiku?

99
17 авг. nustatė Ajeet Ganga 17 rug. 2011-08-17 02:45 „11 at 2:45 am 2011-08-17 02:45
@ 16 atsakymų

Man patinka ši problema. Tai klasikinis interviu klausimas ir, priklausomai nuo to, kaip jūs apie tai galvojate, gausite geriausius ir geriausius sprendimus. Tai tikrai įmanoma padaryti geriau nei O (n 2 ), ir aš išvardijau tris skirtingus būdus, kaip čia galvoti. Tikiuosi, kad šis atsakys į jūsų klausimą!

Pirma, sprendimas „padalina ir užkariauna“. Pažiūrėkime, ar mes galime išspręsti šią problemą, dalindami įvestį per pusę, išsprendžiant problemą kiekviename subarray'e ir tada sujungdami du kartu. Pasirodo, kad mes galime tai padaryti ir galime tai padaryti veiksmingai! Intuicija yra tokia. Jei mes turime vieną dieną, geriausia yra pirkti tą dieną ir tada parduoti tą pačią dieną be pelno. Priešingu atveju padalinkite masyvą į dvi dalis. Jei galvojame, koks būtų optimalus atsakymas, jis turėtų būti vienoje iš trijų vietų:

  • Teisinga pirkimo pora / pardavimas įvyksta per pirmąjį pusmetį.
  • Teisinga pirkimo pora / pardavimas įvyksta antroje pusėje.
  • Teisinga pora pirkti / parduoti yra abiejose pusėse - mes perkame pirmąjį pusmetį, o po to mes parduodame antroje pusėje.

Mes galime gauti reikšmes (1) ir (2), rekursyviai skambindami savo algoritmą pirmoje ir antroje pusėse. Pasirinkus 3 variantą, būdas gauti didžiausią pelną yra pirkti žemiausiame pirmojo pusmečio taške ir parduoti aukščiausiame taške antroje pusėje. Mes galime rasti minimalias ir maksimalias vertes dviejose pusėse paprasčiausiai atlikdami paprastą linijinį nuskaitymą įvestyje ir surandant dvi reikšmes. Tada jis pateikia algoritmą, kurio pasikartojimas yra toks:

 T(1) <= O(1) T(n) <= 2T(n / 2) + O(n) 

Naudojant Meistro teoriją, kad išspręstume šią problemą, mes gauname, kad tai daroma O (n lg n) laiku ir panaudosime O (lg n) rekursiniams skambučiams. Mes tiesiog nugalėjome naivų sprendimą O (n 2 )!

Bet palaukite! Mes galime tai padaryti daug geriau. Atkreipkite dėmesį, kad vienintelė priežastis, kodėl mūsų pakartojime yra O (n) terminalas, yra tai, kad turėjome nuskaityti visą įvestį, stengdamiesi kiekvienoje pusėje rasti minimalias ir maksimalias vertes. Kadangi mes jau rekursiškai tyrinėjame kiekvieną pusę, galbūt galime padaryti daugiau, jei rekursija taip pat grąžins minimalias ir didžiausias kiekvienoje pusėje saugomas vertes! Kitaip tariant, mūsų rekursas grąžina tris dalykus:

  • Pirkimo ir pardavimo laikas, siekiant padidinti pelną.
  • Minimali diapazono vertė.
  • Didžiausia vertė diapazone.

Šios dvi paskutinės reikšmės gali būti apskaičiuojamos rekursiškai naudojant tiesioginį rekursiją, kurį mes galime paleisti vienu metu su rekursija, kad apskaičiuotume (1):

  • Didžiausia ir mažiausia atskiro diapazono vertė yra tik tas elementas.
  • Didžiausias ir mažiausias kelių elementų diapazono reikšmes galima rasti dalijant įvestį į pusę, įvedant kiekvienos pusės maksimalias ir mažiausias vertes, tada imkite atitinkamą maksimumą ir min.

Jei naudojame šį metodą, mūsų pasikartojimo ryšys dabar yra

 T(1) <= O(1) T(n) <= 2T(n / 2) + O(1) 

Naudojant pagrindinį teoremą, mes gauname vykdymo laiką O (n) su tarpu O (lg n), kuris yra dar geresnis nei mūsų originalus sprendimas!

Bet palaukite minutę - mes galime tai padaryti dar geriau! Pagalvokite apie šią problemą sprendžiant dinamišką programavimą. Idėja yra pagalvoti apie šią problemą taip. Tarkime, mes žinojome atsakymą į problemą pažvelgę ​​į pirmuosius k elementus. Ar galime panaudoti savo žinias apie elementą (k + 1) kartu su mūsų pradiniu sprendimu, kad išspręstume pirmųjų (k + 1) elementų problemą? Jei taip, mes galėtume gauti didelį algoritmą, išspręsti pirmojo elemento problemą, tada pirmuosius du, tada pirmuosius tris, ir tt, kol mes apskaičiuojame pirmiesiems n elementams.

Pagalvokite, kaip tai padaryti. Jei turime tik vieną elementą, mes jau žinome, kad tai turėtų būti geriausia pirkimo / pardavimo pora. Tarkime dabar, kad žinome geriausią atsakymą į pirmus k elementus ir apsvarstome elementą (k + 1). Tuomet vienintelis būdas, kaip ši vertė gali sukurti geresnį sprendimą nei pirmieji k elementai, yra tai, kad skirtumas tarp mažiausių pirmųjų k elementų ir naujo elemento yra didesnis už didžiausią skirtumą, kurį apskaičiavome anksčiau iki šiol Tarkime, kad kai einame per elementus, sekame dvi vertybes - minimalią vertę, kurią matėme iki šiol, ir maksimalų pelną, kurį galėtume padaryti tik su pirmais elementais k. Iš pradžių minimali vertė, kurią matėme iki šiol, yra pirmasis elementas, o maksimalus pelnas yra nulis. Kai matome naują elementą, mes pirmą kartą atnaujiname savo optimalų pelną, apskaičiuodami, kiek mes padarysime, perkame už mažiausią kainą, kurią matėme iki šiol, ir parduodant dabartine kaina. Jei tai geriau nei iki šiol apskaičiuota optimali vertė, mes atnaujiname optimalų šio naujo pelno sprendimą. Tada atnaujiname minimalų elementą, kuris iki šiol buvo mažiausias elementas dabartiniam mažiausiam elementui ir naujam elementui.

Kadangi kiekviename žingsnyje mes atliekame tik O (1), o mes kiekvieną kartą n nueisime į kiekvieną n elementą, tai užima O (n) laiką! Be to, ji naudoja tik O (1) pagalbinę saugyklą. Tai taip gerai, kaip iki šiol pasiekėme!

Pavyzdžiui, jūsų įvestyse, kaip šis algoritmas gali veikti. Skaičiai tarp kiekvienos masyvo vertės atitinka reikšmes, saugomas šiame algoritmo taške. Tiesą sakant, jūs to nepadėsite (tai užtruks O (n) atminties!), Tačiau naudinga pamatyti, kaip algoritmas vystosi:

  5 10 4 6 7 min 5 5 4 4 4 best (5,5) (5,10) (5,10) (5,10) (5,10) 

Atsakymas: (5, 10)

  5 10 4 6 12 min 5 5 4 4 4 best (5,5) (5,10) (5,10) (5,10) (4,12) 

Atsakymas: (4, 12)

  1 2 3 4 5 min 1 1 1 1 1 best (1,1) (1,2) (1,3) (1,4) (1,5) 

Atsakymas: (1, 5)

Dabar galime geriau? Deja, ne asimptotine prasme. Jei mes naudojame mažiau O (n) laiko, negalime žiūrėti į visus didelių sąnaudų skaičius ir todėl negalime garantuoti, kad nepraleisime optimalaus atsakymo (mes galėtume paprasčiausiai „paslėpti“ elementus, kurių mes nematėme ). Be to, negalime naudoti mažiau nei O (1) vietos. Gali būti, kad dideli O žymėjime paslėpti nuolatiniai veiksniai bus optimizuoti, tačiau kitaip negalime tikėtis radikaliai geresnių galimybių.

Apskritai tai reiškia, kad turime šiuos algoritmus:

  • Naive: O (n 2 ) laikas, O (1) erdvė.
  • Split ir-Conquer: O (n lg n) laikas, O (lg n).
  • Optimizuotas atskyrimas ir valdymas: laikas O (n), O (lg n).
  • Dinaminis programavimas: O (n) laikas, O (1) erdvė.

Tikiuosi, kad tai padės!

EDIT . Jei domitės, aš kodavau šių keturių „Python“ algoritmų versiją, kad galėtumėte žaisti su jais ir įvertinti jų santykinius rezultatus. Čia yra kodas:

 # Four different algorithms for solving the maximum single-sell profit problem, # each of which have different time and space complexity. This is one of my # all-time favorite algorithms questions, since there are so many different # answers that you can arrive at by thinking about the problem in slightly # different ways. # # The maximum single-sell profit problem is defined as follows. You are given # an array of stock prices representing the value of some stock over time. # Assuming that you are allowed to buy the stock exactly once and sell the # stock exactly once, what is the maximum profit you can make? For example, # given the prices # # 2, 7, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5 # # The maximum profit you can make is 8, by buying when the stock price is 1 and # selling when the stock price is 9. Note that while the greatest difference # in the array is 9 (by subtracting 9 - 0), we cannot actually make a profit of # 9 here because the stock price of 0 comes after the stock price of 9 (though # if we wanted to lose a lot of money, buying high and selling low would be a # great idea!) # # In the event that there no profit to be made at all, we can always buy and # sell on the same date. For example, given these prices (which might # represent a buggy-whip manufacturer:) # # 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 # # The best profit we can make is 0 by buying and selling on the same day. # # Let begin by writing the simplest and easiest algorithm we know of that # can solve this problem - brute force. We will just consider all O(n^2) pairs # of values, and then pick the one with the highest net profit. There are # exactly n + (n - 1) + (n - 2) + ... + 1 = n(n + 1)/2 different pairs to pick # from, so this algorithm will grow quadratically in the worst-case. However, # it uses only O(1) memory, which is a somewhat attractive feature. Plus, if # our first intuition for the problem gives a quadratic solution, we can be # satisfied that if we don't come up with anything else, we can always have a # polynomial-time solution. def BruteForceSingleSellProfit(arr): # Store the best possible profit we can make; initially this is 0. bestProfit = 0; # Iterate across all pairs and find the best out of all of them. As a # minor optimization, we don't consider any pair consisting of a single # element twice, since we already know that we get profit 0 from this. for i in range(0, len(arr)): for j in range (i + 1, len(arr)): bestProfit = max(bestProfit, arr[j] - arr[i]) return bestProfit # This solution is extremely inelegant, and it seems like there just *has* to # be a better solution. In fact, there are many better solutions, and we'll # see three of them. # # The first insight comes if we try to solve this problem by using a divide- # and-conquer strategy. Let consider what happens if we split the array into # two (roughly equal) halves. If we do so, then there are three possible # options about where the best buy and sell times are: # # 1. We should buy and sell purely in the left half of the array. # 2. We should buy and sell purely in the right half of the array. # 3. We should buy in the left half of the array and sell in the right half of # the array. # # (Note that we don't need to consider selling in the left half of the array # and buying in the right half of the array, since the buy time must always # come before the sell time) # # If we want to solve this problem recursively, then we can get values for (1) # and (2) by recursively invoking the algorithm on the left and right # subarrays. But what about (3)? Well, if we want to maximize our profit, we # should be buying at the lowest possible cost in the left half of the array # and selling at the highest possible cost in the right half of the array. # This gives a very elegant algorithm for solving this problem: # # If the array has size 0 or size 1, the maximum profit is 0. # Otherwise: # Split the array in half. # Compute the maximum single-sell profit in the left array, call it L. # Compute the maximum single-sell profit in the right array, call it R. # Find the minimum of the first half of the array, call it Min # Find the maximum of the second half of the array, call it Max # Return the maximum of L, R, and Max - Min. # # Let consider the time and space complexity of this algorithm. Our base # case takes O(1) time, and in our recursive step we make two recursive calls, # one on each half of the array, and then does O(n) work to scan the array # elements to find the minimum and maximum values. This gives the recurrence # # T(1) = O(1) # T(n / 2) = 2T(n / 2) + O(n) # # Using the Master Theorem, this recurrence solves to O(n log n), which is # asymptotically faster than our original approach! However, we do pay a # (slight) cost in memory usage. Because we need to maintain space for all of # the stack frames we use. Since on each recursive call we cut the array size # in half, the maximum number of recursive calls we can make is O(log n), so # this algorithm uses O(n log n) time and O(log n) memory. def DivideAndConquerSingleSellProfit(arr): # Base case: If the array has zero or one elements in it, the maximum # profit is 0. if len(arr) <= 1: return 0; # Cut the array into two roughly equal pieces. left = arr[ : len(arr) / 2] right = arr[len(arr) / 2 : ] # Find the values for buying and selling purely in the left or purely in # the right. leftBest = DivideAndConquerSingleSellProfit(left) rightBest = DivideAndConquerSingleSellProfit(right) # Compute the best profit for buying in the left and selling in the right. crossBest = max(right) - min(left) # Return the best of the three return max(leftBest, rightBest, crossBest) # While the above algorithm for computing the maximum single-sell profit is # better timewise than what we started with (O(n log n) versus O(n^2)), we can # still improve the time performance. In particular, recall our recurrence # relation: # # T(1) = O(1) # T(n) = 2T(n / 2) + O(n) # # Here, the O(n) term in the T(n) case comes from the work being done to find # the maximum and minimum values in the right and left halves of the array, # respectively. If we could find these values faster than what we're doing # right now, we could potentially decrease the function runtime. # # The key observation here is that we can compute the minimum and maximum # values of an array using a divide-and-conquer approach. Specifically: # # If the array has just one element, it is the minimum and maximum value. # Otherwise: # Split the array in half. # Find the minimum and maximum values from the left and right halves. # Return the minimum and maximum of these two values. # # Notice that our base case does only O(1) work, and our recursive case manages # to do only O(1) work in addition to the recursive calls. This gives us the # recurrence relation # # T(1) = O(1) # T(n) = 2T(n / 2) + O(1) # # Using the Master Theorem, this solves to O(n). # # How can we make use of this result? Well, in our current divide-and-conquer # solution, we split the array in half anyway to find the maximum profit we # could make in the left and right subarrays. Could we have those recursive # calls also hand back the maximum and minimum values of the respective arrays? # If so, we could rewrite our solution as follows: # # If the array has size 1, the maximum profit is zero and the maximum and # minimum values are the single array element. # Otherwise: # Split the array in half. # Compute the maximum single-sell profit in the left array, call it L. # Compute the maximum single-sell profit in the right array, call it R. # Let Min be the minimum value in the left array, which we got from our # first recursive call. # Let Max be the maximum value in the right array, which we got from our # second recursive call. # Return the maximum of L, R, and Max - Min for the maximum single-sell # profit, and the appropriate maximum and minimum values found from # the recursive calls. # # The correctness proof for this algorithm works just as it did before, but now # we never actually do a scan of the array at each step. In fact, we do only # O(1) work at each level. This gives a new recurrence # # T(1) = O(1) # T(n) = 2T(n / 2) + O(1) # # Which solves to O(n). We're now using O(n) time and O(log n) memory, which # is asymptotically faster than before! # # The code for this is given below: def OptimizedDivideAndConquerSingleSellProfit(arr): # If the array is empty, the maximum profit is zero. if len(arr) == 0: return 0 # This recursive helper function implements the above recurrence. It # returns a triple of (max profit, min array value, max array value). For # efficiency reasons, we always reuse the array and specify the bounds as # [lhs, rhs] def Recursion(arr, lhs, rhs): # If the array has just one element, we return that the profit is zero # but the minimum and maximum values are just that array value. if lhs == rhs: return (0, arr[lhs], arr[rhs]) # Recursively compute the values for the first and latter half of the # array. To do this, we need to split the array in half. The line # below accomplishes this in a way that, if ported to other > 
238
17 авг. Atsakymą pateikė templatetypedef 17 rug. 2011-08-17 03:02 '11 at 3:02 2011-08-17 03:02

Tai yra didžiausia sumos sekos problema su netiesiogine. Maksimalios subsistemos sumos užduočiai pateikiamas sveikųjų skaičių sąrašas, kuris gali būti teigiamas arba neigiamas, rasti didžiausią nuolatinės šio sąrašo pogrupio sumą.

Šią problemą galite trivialiai konvertuoti į šią problemą, naudodami pelną ar nuostolius tarp einančių dienų. Taigi, pavyzdžiui, turite konvertuoti akcijų kainų sąrašą. [5, 6, 7, 4, 2] pelno / nuostolių sąraše, pavyzdžiui [1, 1, -3, -2] . Po to sekos sekos problema yra gana paprasta išspręsti: suraskite didžiausią masyvo elementų sumą.

31
17 авг. atsakymas pateiktas MSN 17 rug. 2011-08-17 07:11 '11 at 7:11 am 2011-08-17 07:11

Nesu tikras, kodėl tai laikoma dinamiška programavimo problema. Šį klausimą pamačiau vadovėliais ir algoritmais, naudojant erdvę O (n log n) ir O (log n) (pvz., Programavimo interviu elementai). Tai panašu į daug paprastesnę problemą nei žmonės.

Ji veikia stebėdama didžiausią pelną, minimalią pirkimo kainą ir optimalią pirkimo / pardavimo kainą. Kai jis eina per kiekvieną masyvo elementą, jis patikrina, ar tam tikras elementas yra mažesnis už minimalią pirkimo kainą. Jei taip, minimalus pirkimo kainos indeksas ( min ) Atnaujinamas kaip šio elemento indeksas. Be to, kiekvienam elementui becomeABillionaire algoritmas „ becomeABillionaire patikrina, ar arr[i] - arr[min] (skirtumas tarp dabartinio elemento ir minimalios pirkimo kainos) viršija dabartinį pelną. Jei taip, pelnas yra atnaujinamas iki šio skirtumo, o pirkimas yra nustatytas į arr[min] , o pardavimui nustatytas į arr[i] .

Jis atliekamas vienu leidimu.

https://stackoverflow.com/users/599402/ephraim 

5
24 окт. atsakymą pateikė Akash Magoon spalio 24 d. 2015-10-24 09:17 '15 at 9:17 2015-10-24 09:17

čia yra mano „Java“ sprendimas:

 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); } 
2
02 июня '13 в 17:48 2013-06-02 17:48 atsakymą pateikė Rohit Mendiratta 02 birželio 13 d. 5:48 2013-06-02 17:48
 public static double maxProfit(double [] stockPrices) { double initIndex = 0, finalIndex = 0; double tempProfit = list[1] - list[0]; double maxSum = tempProfit; double maxEndPoint = tempProfit; for(int i = 1 ;i<list.length;i++) { tempProfit = list[ i ] - list[i - 1];; if(maxEndPoint < 0) { maxEndPoint = tempProfit; initIndex = i; } else { maxEndPoint += tempProfit; } if(maxSum <= maxEndPoint) { maxSum = maxEndPoint ; finalIndex = i; } } System.out.println(initIndex + " " + finalIndex); return maxSum; } 

Čia yra mano sprendimas. pakeičia maksimalų sekos algoritmą. Решает проблему в O (n). Я думаю, что это невозможно сделать быстрее.

1
ответ дан Afaque 29 апр. '14 в 16:32 2014-04-29 16:32

Максимальная прибыль от одной продажи, решение O (n)

 function stocks_n(price_list){ var maxDif=0, min=price_list[0] for (var i in price_list){ p = price_list[i]; if (p<min) min=p else if (p-min>maxDif) maxDif=p-min; } return maxDif } 

Здесь проект, выполняющий тестирование временной сложности на o (N) vs o (n ^ 2), приближается к набору случайных данных на 100k ints. O (n ^ 2) занимает 2 секунды, а O (n) принимает 0,01 с

https://github.com/gulakov/complexity.js

 function stocks_n2(ps){ for (maxDif=0,i=_i=0;p=ps[i++];i=_i++) for (;p2=ps[i++];) if (p2-p>maxDif) maxDif=p2-p return maxDif }