massimizzazione del profitto per il dato quotazioni di borsa

Question

mi è stato chiesto questa domanda mentre intervistava per una startup e ho visto di nuovo nella recente gara al

Code Sprint:systems

** La domanda:

Ti viene data la i prezzi delle azioni per un insieme di giorni. Ogni giorno puoi acquistare un'unità di azioni, vendere qualsiasi numero di unità di azioni che hai già acquistato o non fare nulla. Qual è il profitto massimo che si può ottenere con la pianificazione della strategia di trading in modo ottimale? **

Esempi (L'ingresso vale a dire il no di giorni può variare)

5 3 2 => profitto = 0 // dato che il prezzo diminuisce ogni giorno, il profitto massimo possiamo fare = 0

1 2 100 => profitto = 197

1 3 1 2 => profitto = 3 // abbiamo comprare a 1 vendere a 3, poi abbiamo acquistare a 1 e vendere a 2 .. profitto totale = 3

La mia soluzione:

a) Trova il giorno in cui il prezzo delle azioni è stato il più grande. Continua a comprare 1 unità di scorta fino a quel giorno.

b) Se tale giorno è l'ultimo giorno quindi chiudere:

altro: vendere tutte le scorte in quel giorno e dividere la matrice dopo quel giorno e ricorsione sugli elementi rimanenti
c) unire i profitti

es 1 4 1 2 3
a) più alto prezzo delle azioni il giorno 2 .. quindi abbiamo acquistare azioni il giorno 1 e venderlo il giorno 2 (utile = 3) poi ricorsivamente nei giorni rimanenti: 1 2 3

b) Il prezzo massimo è 3 (il giorno 5) in modo da continuare a comprare magazzino il giorno 3 e il giorno 4 e vendere il giorno 5 (utile = (3 * 2 - 3 = 3)

c) Totale utile = 3 + 3 = 6

La complessità per questo risulta essere O (n^2). questa soluzione ha superato 10 degli 11 casi ma ha superato il limite di tempo su un ultimo test case (cioè il più grande input)

Quindi la mia domanda è: qualcuno può pensare a una soluzione più efficiente a questo problema? Esiste una soluzione di programmazione dinamica?

P.S: questa è la prima volta che faccio una domanda qui. quindi per favore fammi sapere se ho bisogno di migliorare/aggiungere cose a questa domanda

Answer 1

Sono d'accordo con la logica del tuo metodo, ma non c'è bisogno di eseguire l'elaborazione ricorsiva o le ricerche dei massimi globali. Per trovare i giorni di vendita/acquisto devi solo guardare ogni giorno una volta:

Il trucco è iniziare dalla fine. La compravendita di materie prime è facile se viaggi indietro nel tempo!

Se si pensa che il codice è più facile da leggere delle parole, basta saltare la mia spiegazione, ma qui va:

lettura dalla fine, guarda al prezzo di quel giorno. È questo il prezzo più alto finora (dalla fine), quindi vendere! L'ultimo giorno (dove iniziamo a leggere) venderai sempre.

Quindi andare al giorno successivo (ricordare, indietro nel tempo). È il prezzo più alto finora (da tutti abbiamo guardato ancora)? - Allora vendi tutto, non troverai un giorno migliore. Altrimenti i prezzi aumentano, quindi compra. continuare allo stesso modo fino all'inizio.

L'intero problema è risolto con un unico ciclo inverso: il calcolo sia le decisioni e il profitto del commercio.

Ecco il codice in C-come Python: (ho evitato cose più divinatorio dovrebbe essere leggibile per una persona 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) 

Esempi:

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]) 

Nota che m è il più alto prezzo delle azioni che abbiamo visto (dalla fine). Se ai==m allora il profitto delle azioni acquistate nel passaggio è 0: dopo quel punto avevamo un prezzo decrescente o stabile e non abbiamo acquistato.

È possibile verificare che il calcolo del profitto è corretto con un semplice ciclo (per semplicità immaginate che sia all'interno della funzione di cui sopra)

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) 

Answer 2

Un altro modo di vedere le cose:
In pre-elaborazione, per ogni elemento a[i] trovare a[j] st j > i e massimizza (a[j] - a[i])
così, il migliore si può fare per un prezzo al a[i] è Compra al a[i] e vendere a a[j]. Se non esiste a[j] s.t. a[j] > a[i] quindi a[i] non è affatto un punto di acquisto.

tempo Pre-elaborazione: O(N)

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

Qui, S [i] è il prezzo al quale si deve vendere a [i].

Riassumendo Profitto totale: O(N)

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

Answer 3

la tua logica è corretta ...

vendere a ricorsione maxima's..but globale non è necessaria ...

se esimo elemento è massimo globale ... vendere tutte le scorte prima di me!

Ora problema si riduce alla risposta precedente + i + 1 a N ...

ricorsione non è richiesto ... linearmente possiamo calcolare!

Answer 4

Ho appena risolto il problema in un sito di contest. Penso di avere un algoritmo più semplice della risposta accettata.

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. 

Answer 5

0.Start dalla fine della serie in modo che non c'è bisogno di ricorsione
1. Smax = massimo prezzo delle azioni dalla lista
2.Then trovare il profitto assumendo che avete acquistato tutte le scorte fino Smax e si vendono al prezzo di 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); 


      } 
    } 

Answer 6

il mio ragionamento è, si fanno profitto per ogni azione acquistata prima che il massimo prezzo delle azioni. Utilizzando questa linea di pensiero, si acquista ogni stock prima del prezzo massimo, lo si vende al massimo e si ripete la stessa cosa per i rimanenti prezzi delle azioni.

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; 

} 

Answer 7

Un'altra soluzione O (n) per questo compito può essere fatto utilizzando minimo locale e massima trovare il miglior deferenza (profitto) tra il massimo e il minimo sapendo che max dovrebbe avere una maggiore indice di allora min. Dobbiamo anche esaminare il migliore min locale precedente (implementazione C#).

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

Answer 8

qui è più semplice e facile da capire algo;

private static void BuyOnceAndSellONce() 
    { 
     int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 }; 
     int profit = 0; 
     int minimumPrice = int.MaxValue; 
     for (int i = 0; i < stock.Length; i++) 
     { 
      profit = Math.Max(profit, stock[i] - minimumPrice); 
      minimumPrice = Math.Min(stock[i], minimumPrice); 

     } 
     Console.WriteLine("profit " + profit); 
    } 

    private static void MultipleBuySellButNonOverlappingTransactions() 
    { 
     int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 }; 
     int totalProfit = 0; 
     int currentProfit = 0; 
     for (int i = 1; i < stock.Length;i++) 
     { 
      currentProfit = stock[i] - stock[i - 1]; 
      if (currentProfit > 0) 
       totalProfit += currentProfit; 
     } 

     Console.WriteLine(totalProfit); 
    }