アルゴリズム体操８

13008 ワード
DataStructures Java algorithm array Java テキストリンク

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

説明

毎日の株価（簡単にするための整数）を要素とした配列が渡されて、最大の利益を得るために売買価格を返すアルゴリズムを実装しましょう。
前提条件として、買うと行為が売る行為よりも必ず先に来ることにします。
つまり、もし株価が最小の要素が配列の最後にあるとしても売る価格がその後にないので、その要素は買う価格としては認められません。
単一の売買利益を最大化する必要があります。利益を上げることができない配列が渡された場合は、損失を最小限に抑えようとします。 以下の例では、最大の利益を上げるための売買の価格が黄色と緑で強調されています。二番目の例は損失を最小限にしています。

Hint 『 Kadane's algorithm 』

Solution

Runtime Complexity O(n)

Memory Complexity O(1)

解説

配列の値は、毎日の株価を表します。 １日に一度だけ株式を売買できるので、一定の期間にわたって利益が最大化される
または損失が最小化される、最高の売買価格を見つける必要があります。

力づく解決策はO（n^2）で、各要素とそれに続く要素間の最大利益を見つけることです。

ただ、この問題を実行時間O(n)で片付けることができます。
それは、現在の購入価格（これまでに見られた最小数）、現在の利益(売る価格 - 現在の購入価格)、最大利益を
維持する必要があります。 各反復で、現在の利益をグローバルな利益と比較し、それに応じてグローバルな利益を更新します。
グローバル利益　= 売る価格(反復の中で一番大きい株価) - 買う価格(反復の中で一番小さい株価)

具体例

では具体的な例で実際に見ていきましょう。
まず、初期設定をcurrent_profitを-∞として、buying_priceを配列の最初の要素12、global_sellが配列の二番目の要素5、
そして、gobal_profitがglobal_sell からbuying_priceを引いた数の-7となります。

buying_priceは12より小さいので5に更新され、current_profitはINT_MINより大きいので-7に更新されます

current_profitは4になり、global_profitはglobal_sellと同様に更新されます。 buying_priceは前回の5よりも9の方が大きいので、同じままであることに注意してください。

current_profitは14になり、global_profitはglobal_sellと同様に更新されます。 buying_priceは同じままであることに注意してください。 19を売値として、5（19-14）を買値として返します。

このアルゴリズムのポイントはループでどの変数を毎回更新していくかを決める点。
ループの中で今までの最適な買う価格を保持しつつ、一つ一つの要素を売る価格と見なして現在の利益を更新している。
そして、更新された現在の利益が今までの利益よりも低いか高いかを比較して高ければグローバル利益として更新している。

実装

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

テストの一つ目の配列についてのイメージ図