Algorithmusgymnastik 8

Find Maximum Single Sell Profit (Similar to Max-Subarray)

Erläuterung

Lassen Sie uns einen Algorithmus implementieren, der den Verkaufspreis für maximalen Gewinn zurückgibt und eine Reihe von täglichen Aktienkursen (der Einfachheit halber ganze Zahlen) als Elemente übergibt. Voraussetzung ist, dass der Kauf immer vor dem Verkauf steht. Das heißt, wenn sich das Element mit dem niedrigsten Aktienkurs am Ende des Arrays befindet, gibt es danach keinen Verkaufspreis, sodass dieses Element nicht als Kaufpreis akzeptiert wird. Sie müssen einen einzelnen Handelsgewinn maximieren. Wenn ein Array übergeben wird, das nicht rentabel ist, wird versucht, den Verlust zu minimieren. Im folgenden Beispiel sind die Kauf- und Verkaufspreise für maximalen Gewinn gelb und grün hervorgehoben. Das zweite Beispiel minimiert Verluste.

Hint 『 Kadane's algorithm 』

Solution Runtime Complexity O(n) Memory Complexity O(1)

Kommentar

Die Werte im Array geben den täglichen Aktienkurs an. Sie können Aktien nur einmal am Tag kaufen und verkaufen und so den Gewinn über einen bestimmten Zeitraum maximieren Oder Sie müssen den besten Verkaufspreis finden, der Verluste minimiert.

Die überzeugende Lösung ist O (n ^ 2), um den maximalen Gewinn zwischen jedem Element und den folgenden Elementen zu ermitteln.

Dieses Problem kann jedoch mit der Ausführungszeit O (n) behoben werden. Es ist der aktuelle Kaufpreis (Mindestanzahl jemals gesehen), der aktuelle Gewinn (Verkaufspreis - aktueller Kaufpreis), der maximale Gewinn Muss gepflegt werden. Bei jeder Iteration wird der aktuelle Gewinn mit dem globalen Gewinn verglichen und der globale Gewinn entsprechend aktualisiert. Globaler Gewinn = Verkaufspreis (größter Aktienkurs in der Wiederholung) - Kaufpreis (kleinster Aktienkurs in der Wiederholung)

Konkretes Beispiel

Lassen Sie es uns anhand eines konkreten Beispiels sehen. Erstens ist die Standardeinstellung current_profit auf -∞, purchase_price ist das erste Element 12 des Arrays, global_sell ist das zweite Element 5 des Arrays. Und gobal_profit ist -7, was global_sell minus Kaufpreis ist. Der Kaufpreis ist kleiner als 12, daher wird er auf 5 aktualisiert, und current_profit ist größer als INT_MIN, sodass er auf -7 aktualisiert wird. current_profit ist 4 und global_profit wird aktualisiert sowie global_sell. Beachten Sie, dass der Kaufpreis gleich bleibt, da 9 größer ist als die vorherigen 5. Der aktuelle Gewinn wird 14 sein und der globale Gewinn wird ebenso aktualisiert wie der globale Verkauf. Beachten Sie, dass der Kaufpreis gleich bleibt. Gibt 19 als Verkaufspreis und 5 (19-14) als Kaufpreis zurück.

** Der Zweck dieses Algorithmus besteht darin, zu entscheiden, welche Variable jedes Mal in der Schleife aktualisiert werden soll. Unter Beibehaltung des bisher optimalen Kaufpreises wird jedes Element als Verkaufspreis betrachtet und der aktuelle Gewinn aktualisiert. Wenn der aktualisierte aktuelle Gewinn niedriger oder höher als der vorherige Gewinn ist und wenn er höher ist, wird er als globaler Gewinn aktualisiert. ** ** **

Implementierung

StockPrice.java

public class StockPrices {

    public Tuple find_buy_sell_stock_prices (int[] stock_prices) {

        if (stock_prices == null || stock_prices.length < 2) {
            return null;
        }

        int current_profit  = Integer.MIN_VALUE;
        int global_sell = stock_prices[1];
        int buying_price = stock_prices[0];
        int global_profit = global_sell - buying_price;

        for (int i = 1; i < stock_prices.length; i++) {

            current_profit = stock_prices[i] - buying_price;

            // if true, stock_prices[i] is smaller than global_sell
            if (current_profit > global_profit) {
                global_profit = current_profit;
                global_sell = stock_prices[i];
            }

            if (stock_prices[i] < buying_price){
                buying_price = stock_prices[i];
            }
        }

        Tuple<Integer, Integer> result = new Tuple(global_sell - global_profit, global_sell);
        return result;
    }
}

Tuple.java

class Tuple<X, Y> {
    public X buy;
    public Y sell;

    public Tuple(X x, Y y) {
        this.buy = x;
        this.sell = y;
    }
}

Main.java

public class Main {

    public static void main(String[] args) {
	// write your code here
        StockPrices algorithm = new StockPrices();
        int[] array = {100, 113, 110, 85, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};
        Tuple result = null;
        result = algorithm.find_buy_sell_stock_prices(array);
        System.out.println(String.format("Buy Price: %d Sell Price: %d", result.buy, result.sell));

        int[] array2 = {12,5,9,19,8};
        result = algorithm.find_buy_sell_stock_prices(array2);
        System.out.println(String.format("Buy Price: %d Sell Price: %d", result.buy, result.sell));
    }
}

OUTPUT

Bild der ersten Testsequenz