Best Time to Buy and Sell Stock with Cooldown Solutions in C++

// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
// Author : Hao Chen
// Date   : 2019-02-01


class Solution {
public:
    //
    //Define 
    //
    //  - buy[i] as the max profit when you buy the stock at day i. 
    //  - sell[i] as the max profit when you sell the stock at day i. 
    //
    // Therefore set buy[0] = -prices[0], because spend the money, the profit is -prices[0].
    // Also set sell[0] = 0, that you do nothing in the first day.
    //
    // So,
    //     buy[i] = max(buy[i-1],                // do nothing - keep holding
    //                  sell[i-2] - prices[i] )  // sell previous day, buy today
    //                                           // i-1 is cooldown day
    //     sell[i] = max(sell[i-1],              // do nothing 
    //                   buy[i-1] + prices[i] )  // buy previous day, sell today.
    //  
    
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if ( len < 2 ) return 0;
        
        vector<int> buy(len, 0);
        vector<int> sell(len, 0);
        
        //day 0
        buy[0] = -prices[0];
        sell[0] = 0;
        
        //day 1
        buy[1] = max(buy[0], 0 - prices[1]);
        sell[1] = max(sell[0], buy[0] + prices[1]);
        
        for (int i=2; i<len; i++) {
            buy[i]  = max( buy[i - 1], sell[i - 2] - prices[i]);   
            sell[i] = max(sell[i - 1],  buy[i - 1] + prices[i]);
        }
        
        return sell[len-1];
    }
};

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
/// Author : liuyubobobo
/// Time   : 2019-06-27

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

private:
    int n;

public:
    int maxProfit(vector<int>& prices) {

        n = prices.size();
        if(n <= 1) return 0;

        vector<int> buy(n, -1), sell(n, -1);
        return _sell(prices, n - 1, buy, sell);
    }

private:
    int _sell(const vector<int>& prices, int index, vector<int>& buy, vector<int>& sell){

        if(index == 0) return 0;
        if(index == 1) return max(0, prices[1] - prices[0]);

        if(sell[index] != -1) return sell[index];
        return sell[index] = max(_sell(prices, index - 1, buy, sell),
                                 _buy(prices, index - 1, buy, sell) + prices[index]);
    }

    int _buy(const vector<int>& prices, int index, vector<int>& buy, vector<int>& sell){

        if(index == 0) return -prices[0];
        if(index == 1) return max(-prices[0], -prices[1]);

        if(buy[index] != -1) return buy[index];
        return buy[index] = max(_buy(prices, index - 1, buy, sell),
                                _sell(prices, index - 2, buy, sell) - prices[index]);
    }
};


int main() {

    vector<int> prices1 = {1, 2, 3, 0, 2};
    cout << Solution().maxProfit(prices1) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
/// Author : liuyubobobo
/// Time   : 2017-10-23

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        if(prices.size() <= 1)
            return 0;

        vector<int> buy(prices.size(), 0);
        vector<int> sell(prices.size(), 0);

        buy[0] = -prices[0];
        buy[1] = max(-prices[0], -prices[1]);
        sell[1] = max(0, buy[0] + prices[1]);
        for(int i = 2 ; i < prices.size() ; i ++){
            sell[i] = max(sell[i-1], buy[i-1] + prices[i]);
            buy[i] = max(buy[i-1], sell[i-2] - prices[i]);
        }

        return sell.back();
    }
};


int main() {

    vector<int> prices1 = {1, 2, 3, 0, 2};
    cout << Solution().maxProfit(prices1) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
/// Author : liuyubobobo
/// Time   : 2017-10-24

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming with Space Optimization
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int n = prices.size();

        if(n <= 1)
            return 0;

        int buy[3] = {-prices[0], max(-prices[0], -prices[1]), 0};
        int sell[3] = {0, max(0, prices[1] - prices[0]), 0};

        for(int i = 2 ; i < n ; i ++){
            sell[i % 3] = max(sell[(i - 1) % 3], buy[(i - 1) % 3] + prices[i]);
            buy[i % 3] = max(buy[(i - 1) % 3], sell[(i - 2) % 3] - prices[i]);
        }

        return sell[(n - 1) % 3];
    }
};


int main() {

    vector<int> prices1 = {1, 2, 3, 0, 2};
    cout << Solution().maxProfit(prices1) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
/// Author : liuyubobobo
/// Time   : 2020-05-25

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Using three states every day
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int n = prices.size();

        if(n <= 1)
            return 0;

        vector<vector<int>> dp(n, vector<int>(3, 0)); // 0 hold; 1 sell(cooldown); 2 unhold
        dp[0][0] = -prices[0];

        for(int i = 1 ; i < n ; i ++){
            dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][2] - prices[i]), dp[i - 1][1] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
        }

        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};


int main() {

    vector<int> prices1 = {1, 2, 3, 0, 2};
    cout << Solution().maxProfit(prices1) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
/// Author : liuyubobobo
/// Time   : 2020-05-25

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Using three states every day, with space optimization
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int n = prices.size();

        if(n <= 1)
            return 0;

        int hold = -prices[0], sell = 0, unhold = 0;

        for(int i = 1 ; i < n ; i ++){
            hold = max(hold, unhold - prices[i]);
            unhold = max(sell, unhold);
            sell = hold + prices[i];
        }

        return max(unhold, sell);
    }
};


int main() {

    vector<int> prices1 = {1, 2, 3, 0, 2};
    cout << Solution().maxProfit(prices1) << endl;
    // 3

    return 0;
}