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

테스트의 첫 번째 배열에 대한 이미지 다이어그램