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. Screen Shot 2019-12-21 at 11.14.07.png

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. Screen Shot 2019-12-21 at 11.46.15.png 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. Screen Shot 2019-12-21 at 11.52.21.png 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. Screen Shot 2019-12-21 at 11.53.11.png 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. Screen Shot 2019-12-21 at 11.55.00.png

** 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 Screen Shot 2019-12-21 at 11.58.16.png

Image of the first sequence of tests Screen Shot 2019-12-21 at 12.00.39.png

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm