[JAVA] Algorithm gymnastics 8

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

Description

Let's implement an algorithm that returns a buy / sell price for maximum profit, passed an array with daily stock prices (integers for simplicity) as elements. As a prerequisite, the act of buying always comes before the act of selling. That is, if the element with the lowest stock price is at the end of the array, there is no selling price after that, so that element is not accepted as a buying price. You need to maximize your single trading profit. If an array is passed that is not profitable, it will try to minimize the loss. In the example below, the buy and sell prices for maximum profit are highlighted in yellow and green. The second example minimizes losses.

Hint 『 Kadane's algorithm 』

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

Commentary

The values in the array represent the daily stock price. You can buy and sell stocks only once a day, maximizing your profits over a period of time. Or you need to find the best selling price that minimizes the loss.

The compelling solution is O (n ^ 2), which is to find the maximum profit between each element and the elements that follow it.

However, this problem can be cleared up with execution time O (n). It is the current purchase price (minimum number ever seen), current profit (selling price-current purchase price), maximum profit. Must be maintained. At each iteration, the current profit is compared to the global profit and the global profit is updated accordingly. Global profit = Selling price (largest stock price in the iteration) --Buying price (smallest stock price in the iteration)

Concrete example

Let's actually see it with a concrete example. First, the initial setting is current_profit to -∞, buying_price is the first element 12 of the array, global_sell is the second element 5 of the array, And gobal_profit is -7, which is global_sell minus buying_price. buying_price is less than 12, so it is updated to 5, and current_profit is greater than INT_MIN, so it is updated to -7. current_profit will be 4 and global_profit will be updated as well as global_sell. Note that buying_price remains the same as 9 is greater than the previous 5. The current_profit will be 14 and global_profit will be updated as well as global_sell. Note that buying_price remains the same. Returns 19 as the ask price and 5 (19-14) as the bid price.

** The point of this algorithm is to decide which variable to update each time in the loop. While maintaining the optimal buying price so far in the loop, it considers each element as the selling price and updates the current profit. Then, if the updated current profit is lower or higher than the previous profit, and if it is higher, it is updated as a global profit. ** **

Implementation

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 of the first sequence of tests