wake-up-neo.com

Gewinnmaximierung für gegebene Aktienkurse

Diese Frage wurde mir während eines Interviews für ein Startup gestellt und im letzten Contest bei gesehen 

Code Sprint: Systeme

**Die Frage :

Sie erhalten die Aktienkurse für eine Reihe von Tagen. Jeden Tag können Sie entweder eine Aktie kaufen, eine beliebige Anzahl von Aktien kaufen, die Sie bereits gekauft haben, oder nichts tun. Was ist der maximale Gewinn, den Sie erzielen können, wenn Sie Ihre Handelsstrategie optimal planen? **

Beispiele (die Eingabe, dh die Anzahl der Tage kann variieren)

5 3 2 => profit = 0 // da der preis jeden tag sinkt, ist der maximale gewinn, den wir erzielen können, = 0 

1 2 100 => Gewinn = 197 

1 3 1 2 => Gewinn = 3 // Wir kaufen bei 1, verkaufen bei 3, kaufen dann bei 1 und verkaufen bei 2 .. Gesamtgewinn = 3 

Meine Lösung : 

a) Finden Sie den Tag, an dem der Aktienkurs am größten war. Kaufen Sie bis zu diesem Tag 1 Einheit vor. 

b) Wenn dieser Tag der letzte Tag ist, dann beenden Sie: 

sonst: Verkaufen Sie alle Aktien an diesem Tag und teilen Sie das Array nach diesem Tag auf, und informieren Sie sich über die restlichen Elemente
c) den Gewinn zusammenführen 

z.B. 1 4 1 2 3
a) höchster Aktienkurs am 2. Tag. Also kaufen wir Aktien am ersten Tag und verkaufen sie am zweiten Tag (Gewinn = 3)

b) Maximalpreis ist 3 (am Tag 5), also kaufen wir am Tag 3 und am Tag 4 weiter Aktien und verkaufen am Tag 5 (Gewinn = (3 * 2 - 3 = 3) 

c) Gesamtgewinn = 3 + 3 = 6 

Die Komplexität hierfür stellt sich als O (n ^ 2) heraus. Diese Lösung bestand 10 der 11 Fälle, überschritt jedoch die Zeitgrenze für einen letzten Testfall (d. h. die größte Eingabe). 

Meine Frage ist also, kann sich jemand eine effizientere Lösung für dieses Problem vorstellen? Gibt es eine dynamische Programmierlösung? 

P.S: Dies ist das erste Mal, dass ich hier eine Frage stelle. Bitte lassen Sie mich wissen, ob ich diese Frage verbessern oder ergänzen muss 

38
thor_hayek

Ich stimme mit der Logik Ihrer Methode überein, aber es ist nicht notwendig, rekursive Verarbeitung oder globale Maxima-Suchen durchzuführen. Um die Verkaufs-/Kauftage zu finden, müssen Sie sich jeden Tag nur einmal ansehen:

Der Trick besteht darin, am Ende zu beginnen. Aktienhandel ist einfach, wenn Sie rechtzeitig zurück reisen!

Wenn Sie denken, dass Code leichter zu lesen ist als Wörter, überspringen Sie einfach meine Erklärung, aber hier ist:

Lesen Sie von Ende bis zum Tagespreis. Ist dies der bisher höchste Preis (vom Ende), dann verkaufen! Den letzten Tag (an dem wir anfangen zu lesen) werden Sie immer verkaufen. 

Gehen Sie dann zum nächsten Tag (denken Sie daran, in der Zeit rückwärts). Ist es der bisher höchste Preis (von allen, die wir bisher angesehen haben)? - Dann verkaufen Sie alles, Sie werden keinen besseren Tag finden. Sonst steigen die Preise, also kaufen. weiter bis zum anfang. 

Das gesamte Problem wird mit einer einzigen Umkehrschleife gelöst: Es werden sowohl die Entscheidungen als auch der Profit des Handels berechnet.

Hier ist der Code in C-artigem Python: (Ich habe die meisten Pythonic-Sachen vermieden. Sollte für eine C-Person lesbar sein)

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)  

Beispiele:

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

Beachten Sie, dass m der höchste Aktienkurs ist, den wir gesehen haben (vom Ende). Wenn ai==m, dann ist der Gewinn aus Aktien, die in der Stufe gekauft wurden, 0: Wir hatten ab diesem Zeitpunkt einen abnehmenden oder stabilen Preis und kauften nicht.

Sie können mit einer einfachen Schleife überprüfen, ob die Gewinnberechnung korrekt ist (stellen Sie sich der Einfachheit halber vor, dass sie innerhalb der obigen Funktion liegt)

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)
55
Johan Lundberg

Eine andere Sichtweise: 
In der Vorverarbeitung finden Sie für jedes Element a[i] find a[j] s.t. j > i und maximiert (a[j] - a[i]) 
Also, dieBeste, die Sie für einen Preis bei a[i] tun können, ist Kaufen bei a[i] und Verkaufen bei a[j]. Wenn es keinen a[j] s.t. a[j] > a[i] dann a[i] ist überhaupt kein Kaufpunkt.

Vorlaufzeit: O(N) 

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

Hier ist S [i] der Preis, zu dem Sie ein [i] verkaufen sollten. 

Gesamter Gewinn zusammenfassen: O(N)

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

Eine andere O(n) - Lösung für diese Aufgabe kann durch Verwenden des lokalen Minimums und Maximums durchgeführt werden, um die beste Rücksicht (Gewinn) zwischen Max und Min zu finden, wissend, dass Max einen größeren Index als Min haben sollte. Wir müssen auch die bisher beste lokale Min (C # -Implementierung) betrachten. 

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

0.Starten Sie vom Ende des Arrays, damit keine Rekursion erforderlich ist
1. smax = maximaler Aktienkurs aus der Liste
2. Dann finden Sie den Gewinn, indem Sie davon ausgehen, dass Sie alle Aktien bis smax gekauft haben. und Sie verkaufen es zum Preis von 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);


          }
   }
3
Tokala Sai Teja

Ich habe dieses Problem gerade in einer Contest-Site gelöst. Ich denke, ich habe einen einfacheren Algorithmus als die akzeptierte Antwort.

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.
2

hier ist einfacher und leichter zu verstehen 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);
    }
0
AvtarSohi
private static int MaxProfit(int[] A)
        {
            if (A.Length == 0)
                return 0;
            Stack<int> repositoryStack = new Stack<int>();
            int maxProfit = 0;
            int tempProfit;
            for (int i = 0; i < A.Length; i++)
            {
                if (repositoryStack.Count == 0)
                {
                    repositoryStack.Push(i);
                    continue;
                }
                while (repositoryStack.Count != 0 && A[i] < A[repositoryStack.Peek()])
                {
                    repositoryStack.Pop();
                }
                if (repositoryStack.Count != 0 && A[i] > A[repositoryStack.Peek()])
                {
                    tempProfit = A[i] - A[repositoryStack.Peek()];
                    if (tempProfit > maxProfit)
                        maxProfit = tempProfit;
                }
                if(repositoryStack.Count == 0)
                    repositoryStack.Push(i);
            }
            return maxProfit;
        }
0
Mohamed.Emad

deine Logik ist richtig ...

bei global maxima's verkaufen ... aber Rekursion ist nicht erforderlich ...

wenn das Element globale Maxima ist ... verkaufe alle Aktien bevor ich!

Jetzt reduziert sich das Problem auf die vorherige Antwort + i + 1 auf N ...

rekursion ist nicht erforderlich ... linear können wir berechnen!

0
Shivendra