Best Time to Buy and Sell Stock

• https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Tag: Greedy

Problem Description

Buy and sell just once

Takes an array denoting the daily stock price, and returns the maximum profit that could be made by buying and then selling one share of that stock.

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    int minPrice = Integer.MAX_VALUE;

    for (int price : prices) {
        maxProfit = Math.max(maxProfit, price - minPrice);
        minPrice = Math.min(minPrice, price);
    }
    return maxProfit;
}

Buy and sell as many as you want

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public int maxProfit(int[] prices) {
    int profits = 0;
    int diff = 0;

    for (int i = 1; i < prices.length; i++) {
        diff = prices[i] - prices[i - 1];
        if (diff > 0)
            profits += diff;
    }
    return profits;
}

Buy and sell at most twice

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution description

one-dimensional dynamica problem

maxprofit [i] = maxprofit[0-i] = maxprofit[i-n]

We can do it with two passes, first forward scan then backward.

public int maxProfitNoMoreThanTwice(int[] prices) {
    int maxProfit = 0;
    int minPrice = Integer.MAX_VALUE;
    int[] firstBuyProfits = new int[prices.length];


    for (int i = 0; i < prices.length; i++) {
        int price = prices[i];
        maxProfit = Math.max(maxProfit, price - minPrice);
        minPrice = Math.min(minPrice, price);
        firstBuyProfits[i] = maxProfit;
    }

    int maxTotalProfit = maxProfit;
    // Backward phase. For each day, find the maximum profit if we make
    // the second buy on that day.
    int maxPriceSoFar = Integer.MIN_VALUE;
    for (int i = prices.length - 1; i > 0; i--) {
        maxPriceSoFar = Math.max(maxPriceSoFar, prices[i]);

        maxTotalProfit =
                Math.max(maxTotalProfit, maxPriceSoFar - prices[i] +
                        firstBuyProfits[i - 1]);
    }

    return maxTotalProfit;
}