LeetCode - Best Time to Buy and Sell Stock III


LeetCode 121 - Best Time to Buy and Sell Stock
LeetCode - Best Time to Buy and Sell Stock II
LeetCode - Best Time to Buy and Sell Stock III
LeetCode 188 - Best Time to Buy and Sell Stock IV

Leetcode 309 - Best Time to Buy and Sell Stock with Cooldown
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.
Notice
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example
Given an example [4,4,6,1,1,4,2,5], return 6.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/135704/Detail-explanation-of-DP-solution
It's not difficult to get the DP recursive formula:
dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j-1]), j=[0..i-1]
For k transactions, on i-th day,
if we don't trade then the profit is same as previous day dp[k, i-1];
and if we bought the share on j-th day where j=[0..i-1], then sell the share on i-th day then the profit is prices[i] - prices[j] + dp[k-1, j-1] .
Actually j can be i as well. When j is i, the one more extra item prices[i] - prices[j] + dp[k-1, j] = dp[k-1, i] looks like we just lose one chance of transaction.
I see someone else use the formula dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j]), where the last one is dp[k-1, j] instead of dp[k-1, j-1]. It's not the direct sense, as if the share was bought on j-th day, then the total profit of previous transactions should be done on (j-1)th day. However, the result based on that formula is also correct, because if the share was sold on j-th day and then bought again, it is the same if we didn't trade on that day.
So the straigtforward implementation is:
        public int MaxProfitDp(int[] prices) {
            if (prices.Length == 0) return 0;
            var dp = new int[3, prices.Length];
            for (int k = 1; k <= 2; k++)  {
                for (int i = 1; i < prices.Length; i++) {
                    int min = prices[0];
                    for (int j = 1; j <= i; j++)
                        min = Math.Min(min, prices[j] - dp[k-1, j-1]);
                    dp[k, i] = Math.Max(dp[k, i-1], prices[i] - min);
                }
            }

            return dp[2, prices.Length - 1];
        }
Time complexity is O(kn^2), space complexity is O(kn).
In the above code, min is repeated calculated. It can be easily improved as:
        public int MaxProfitDpCompact1(int[] prices) {
            if (prices.Length == 0) return 0;
            var dp = new int[3, prices.Length];
            for (int k = 1; k <= 2; k++) {
                int min = prices[0];
                for (int i = 1; i < prices.Length; i++) {
                    min = Math.Min(min, prices[i] - dp[k-1, i-1]);
                    dp[k, i] = Math.Max(dp[k, i-1], prices[i] - min);
                }
            }

            return dp[2, prices.Length - 1];
        }
Time complexity is O(kn), space complexity is O(kn).
If we slight swap the two 'for' loops:
        public int MaxProfitDpCompact1T(int[] prices) {
            if (prices.Length == 0) return 0;
            var dp = new int[3, prices.Length];
            var min = new int[3];
            Array.Fill(min, prices[0]);
            for (int i = 1; i < prices.Length; i++) {
                for (int k = 1; k <= 2; k++) {
                    min[k] = Math.Min(min[k], prices[i] - dp[k-1, i-1]);
                    dp[k, i] = Math.Max(dp[k, i-1], prices[i] - min[k]);
                }
            }

            return dp[2, prices.Length - 1];
        }
We need to save min for each transaction, so there are k 'min'.
We can find the second dimension (variable i) is only dependent on the previous one (i-1), so we can compact this dimension. (We can choose the first dimension (variable k) as well since it is also only dependent on its previous one k-1, but can't compact both.)
        public int MaxProfitDpCompact2(int[] prices) {
            if (prices.Length == 0) return 0;
            var dp = new int[3];
            var min = new int[3];
            Array.Fill(min, prices[0]);
            for (int i = 1; i < prices.Length; i++)  {
                for (int k = 1; k <= 2; k++) {
                    min[k] = Math.Min(min[k], prices[i] - dp[k-1]);
                    dp[k] = Math.Max(dp[k], prices[i] - min[k]);
                }
            }

            return dp[2];
        }
So time complexity is O(kn), space complexity becomes O(k).
In this case, K is 2. We can expand the array to all named variables:
        public int MaxProfitDpCompactFinal(int[] prices)  {
            int buy1 = int.MaxValue, buy2 = int.MaxValue;
            int sell1 = 0, sell2 = 0;

            for (int i = 0; i < prices.Length; i++) {
                buy1 = Math.Min(buy1, prices[i]);
                sell1 = Math.Max(sell1, prices[i] - buy1);
                buy2 = Math.Min(buy2, prices[i] - sell1);
                sell2 = Math.Max(sell2, prices[i] - buy2);
            }

            return sell2;
        }
We can also explain the above codes in other words. On every day, we buy the share with the price as low as we can, and sell the share with price as high as we can. For the second transaction, we integrate the profit of first transaction into the cost of the second buy, then the profit of the second sell will be the total profit of two transactions

X. O(1) space
https://discuss.leetcode.com/topic/5934/is-it-best-solution-with-o-n-o-1
The thinking is simple and is inspired by the best solution from Single Number II (I read through the discussion after I use DP).
Assume we only have 0 money at first;
4 Variables to maintain some interested 'ceilings' so far:
The maximum of if we've just buy 1st stock, if we've just sold 1nd stock, if we've just buy 2nd stock, if we've just sold 2nd stock.
Very simple code too and work well. I have to say the logic is simple than those in Single Number II.
release2 means you can sell it at most two transactions, which already includes the once case.This is because the hold2 value comes from Math.max(hold2, release1-i).If there is only one peak, hold2 is always equal to hold1.

    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far. 
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
First assume that we have no money, so buy1 means that we have to borrow money from others, we want to borrow less so that we have to make our balance as max as we can(because this is negative).
sell1 means we decide to sell the stock, after selling it we have price[i] money and we have to give back the money we owed, so we have price[i] - |buy1| = prices[i ] + buy1, we want to make this max.
buy2 means we want to buy another stock, we already have sell1 money, so after buying stock2 we have buy2 = sell1 - price[i] money left, we want more money left, so we make it max
sell2 means we want to sell stock2, we can have price[i] money after selling it, and we have buy2 money left before, so sell2 = buy2 + prices[i], we make this max.
So sell2 is the most money we can have.
To understand the hidden logic, you have to understand what these 4 variables stand for.
sell2: Final profit.
buy2: Best profit so far, if you buy the stock not after Day i (2nd transaction).
sell1: Best profit so far, if you sell the stock not after Day i (1st transaction).
buy1: Minimum price to buy the stock.
The logic between buy1 and sell1 is quite straight forward. What you need to do is simply find a minimum price to buy and sell it some days after.
Of course, sell1 won't update if the profit is not greater than before even if you buy the stock at a lower price. Let's assume you sell the stock at Day a to get the greatest profit for the 1st transaction, which stores in sell1.
Now comes the trick. Assume you find a better deal at Day b, sell1 get updated. So you have 2 choice for buy2:
  • not update buy2, you still sell your stock at Day a. Nothing changed.
  • update buy2 with new sell1, which means you sell the stock at Day b.
    buy2 = sell1 - price[i] means you sell you stock at Day b and buy it at Day i. And Day i is definitely not early than Day b, which is the hidden logic.
public int maxProfit(int[] prices) {
  int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
  for (int i = 0; i < prices.length; i++) {
   buy1 = Math.max(buy1, -prices[i]);
   sell1 = Math.max(sell1, buy1 + prices[i]);
   buy2 = Math.max(buy2, sell1 - prices[i]);
   sell2 = Math.max(sell2, buy2 + prices[i]);
  }
  return sell2;
 }
public int maxProfit(int[] prices) {
    // these four variables represent your profit after executing corresponding transaction
    // in the beginning, your profit is 0. 
    // when you buy a stock ,the profit will be deducted of the price of stock.
    int firstBuy = Integer.MIN_VALUE, firstSell = 0;
    int secondBuy = Integer.MIN_VALUE, secondSell = 0;

    for (int curPrice : prices) {
        if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
        if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
        if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
        if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
    }
    
    return secondSell; // secondSell will be the max profit after passing the prices
}

public int maxProfit(int[] prices) {
    // these four variables represent your profit after executing corresponding transaction
    // in the beginning, your profit is 0. 
    // when you buy a stock ,the profit will be deducted of the price of stock.
    int firstBuy = Integer.MIN_VALUE, firstSell = 0;
    int secondBuy = Integer.MIN_VALUE, secondSell = 0;

    
    // (-firstBuy) is min value beteen [0, curPrice.index], firstBuy itself is a negative value
    
    // (firstSell) is max profit between [0, current.index], before update it is max profit between [0, current.index-1], after update is max(firstSell.before, curPrice + firstBuy(e.g. - minValue[0, curPrice.index]))
    
    // (secondBuy) is max profit between [0,curPrice.index] under seen prices if you hold/buy a stock between[0, curPrice.index] and haven't sell it yet.
    
    // (secondSell) is max profit between [0,curPrice.index] under seen prices if you buy a second stock between [0,curPrice.index];
    
    for (int curPrice : prices) {
        if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
        if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
        if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
        if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
    }
    
    return secondSell; // secondSell will be the max profit after passing the prices
}

X. Left + Right Array
we can use two arrays f[i] and b[i] to record the maximum profit for price[0...i−1] and price[i...n−1] , respectively. After that, we just need to find the maximum of f[i]+b[i]
public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        // forward[i]: maximum profit for prices[0...i-1]; forward[0]=0
        int[] forward = new int[prices.length+1];
        int lowestBuyInPrice = prices[0];   // Lowest buy-in price up to now
        for (int i = 2; i <= prices.length; i++) {      // Traverse forwards
            forward[i] = Math.max(forward[i-1], prices[i-1]-lowestBuyInPrice);
            lowestBuyInPrice = Math.min(lowestBuyInPrice, prices[i-1]);
        }
        // backward[i]: maximum profit for prices[i...n-1]
        int[] backward = new int[prices.length];
        int highestSellOutPrice = prices[prices.length-1];   // Lowest buy-in price up to now
        for (int i = prices.length-2; i >= 0; i--) {    // Traverse backwards
            backward[i] = Math.max(backward[i+1], highestSellOutPrice-prices[i]);
            highestSellOutPrice = Math.max(highestSellOutPrice, prices[i]);
        }
        // Find the maximum of forward[i]+backward[i]
        int maximumProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maximumProfit = Math.max(maximumProfit, forward[i]+backward[i]);
        }
        return maximumProfit;
    }
https://xuezhashuati.blogspot.com/2017/04/lintcode-151-best-time-to-buy-and-sell.html
最多2次买卖。
我们从左到右，在每一个i计算：
如果只能一次买卖，从第0天到第i天，能获得的最大利润是多少。
我们再从右到左，在每一个i计算：
如果只能买卖一次，从第i天到最后一天，能获得的最大利润是多少。

我们可以知道，在任何一天i，我们最多2次买卖的最大利润，是从第0天到第i天有最多1次买卖的最大利润，加上从第i天到最后一天有最多1次买卖的最大利润。
    public int maxProfit(int[] prices) {        
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        left[0] = 0;
        right[prices.length - 1] = 0;
        
        int min = prices[0];
        int max = prices[prices.length - 1];
        
        for (int i = 1; i < prices.length; i++) {
            left[i] = Math.max(left[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        
        for (int i = prices.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
        
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        
        return maxProfit;
    }
https://www.jiuzhang.com/solutions/best-time-to-buy-and-sell-stock-iii/
http://www.programcreek.com/2014/02/leetcode-best-time-to-buy-and-sell-stock-iii-java/
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int[] left = new int[prices.length];
        int[] right = new int[prices.length];

        // DP from left to right;
        left[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            left[i] = Math.max(left[i - 1], prices[i] - min);
        }

        //DP from right to left;
        right[prices.length - 1] = 0;
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            max = Math.max(prices[i], max);
            right[i] = Math.max(right[i + 1], max - prices[i]);
        }

        int profit = 0;
        for (int i = 0; i < prices.length; i++){
            profit = Math.max(left[i] + right[i], profit);  
        }
        return profit;
    }
http://blog.csdn.net/fightforyourdream/article/details/14503469

https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions
Solution is commented in the code. Time complexity is O(kn), space complexity can be O(n) because this DP only uses the result from last step. But for cleaness this solution still used O(kn) space complexity to preserve similarity to the equations in the comments.
    int maxProfit(vector<int> &prices) {
        // f[k, ii] represents the max profit up until prices[ii] (Note: NOT ending with prices[ii]) using at most k transactions. 
        // f[k, ii] = max(f[k, ii-1], prices[ii] - prices[jj] + f[k-1, jj]) { jj in range of [0, ii-1] }
        //          = max(f[k, ii-1], prices[ii] + max(f[k-1, jj] - prices[jj]))
        // f[0, ii] = 0; 0 times transation makes 0 profit
        // f[k, 0] = 0; if there is only one price data point you can't make any money no matter how many times you can trade
        if (prices.size() <= 1) return 0;
        else {
            int K = 2; // number of max transation allowed
            int maxProf = 0;
            vector<vector<int>> f(K+1, vector<int>(prices.size(), 0));
            for (int kk = 1; kk <= K; kk++) {
                int tmpMax = f[kk-1][0] - prices[0];
                for (int ii = 1; ii < prices.size(); ii++) {
                    f[kk][ii] = max(f[kk][ii-1], prices[ii] + tmpMax);
                    tmpMax = max(tmpMax, f[kk-1][ii] - prices[ii]);
                    maxProf = max(f[kk][ii], maxProf);
                }
            }
            return maxProf;
        }
    }
Read full article from LeetCode - Best Time to Buy and Sell Stock III | Darren's Blog
at
Labels: , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts