Gymnastique algorithmique 8

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

La description

Implémentons un algorithme qui renvoie le prix d'achat et de vente pour un profit maximum, passé un tableau avec les cours quotidiens des actions (entiers pour plus de simplicité) comme éléments. Comme condition préalable, l'acte d'achat précède toujours l'acte de vente. Autrement dit, même si l'élément avec le cours de l'action le plus bas se trouve à la fin du tableau, il n'y a pas de prix de vente après cela, de sorte que cet élément n'est pas accepté comme prix d'achat. Vous devez maximiser un seul profit commercial. Si un tableau est passé qui n'est pas rentable, il essaiera de minimiser la perte. Dans l'exemple ci-dessous, les prix d'achat et de vente pour un profit maximum sont surlignés en jaune et vert. Le deuxième exemple minimise les pertes.

Hint 『 Kadane's algorithm 』

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

Commentaire

Les valeurs du tableau représentent le cours quotidien de l'action. Vous ne pouvez acheter et vendre des actions qu'une fois par jour, maximisant ainsi les bénéfices sur une période donnée Ou vous devez trouver le meilleur prix de vente qui minimise les pertes.

La solution incontournable est O (n ^ 2) pour trouver le profit maximum entre chaque élément et les éléments qui suivent.

Cependant, ce problème peut être résolu avec le temps d'exécution O (n). C'est le prix d'achat actuel (nombre minimum jamais vu), le profit actuel (prix de vente-prix d'achat actuel), le profit maximum Doit être entretenu. À chaque itération, le profit actuel est comparé au profit global et le profit global est mis à jour en conséquence. Bénéfice global = Prix de vente (prix de l'action le plus élevé en répétition) - Prix d'achat (prix de l'action le plus petit en répétition)

Exemple concret

Voyons cela avec un exemple concret. Premièrement, le paramètre par défaut est current_profit à -∞, achat_price est le premier élément 12 du tableau, global_sell est le deuxième élément 5 du tableau, Et gobal_profit vaut -7, ce qui correspond à global_sell moins achat_price. buy_price est inférieur à 12, il est donc mis à jour à 5 et current_profit est supérieur à INT_MIN, il est donc mis à jour à -7. current_profit sera égal à 4 et global_profit sera mis à jour ainsi que global_sell. Notez que le prix d'achat reste le même car 9 est plus grand que le 5 précédent. Le current_profit sera 14, et global_profit sera mis à jour ainsi que global_sell. Notez que le prix d'achat reste le même. Renvoie 19 comme prix de vente et 5 (19-14) comme prix d'achat.

** Le but de cet algorithme est de décider quelle variable mettre à jour à chaque fois dans la boucle. Tout en maintenant le prix d'achat optimal jusqu'à présent dans la boucle, il considère chaque élément comme le prix de vente et met à jour le profit actuel. Ensuite, si le profit actuel mis à jour est inférieur ou supérieur au profit précédent, et s'il est supérieur, il est mis à jour en tant que profit global. ** **

la mise en oeuvre

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

Image de la première séquence de tests