Best Time to Buy and Sell Stock IV Solutions in C++

// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
// Author : Hao Chen
// Date   : 2015-03-31



class Solution {
    public:
        /*
         *  profits[trans, day]
         *  - `trans` represents the number of transactions we've done so far. ( 0 <= trans <= k )
         *  - `day` represents the number of days so far. ( 0 <= day <= prices.size() )
         *
         *  So, we have the initialization as below:
         *
         *  profits[0, day] = 0; // 0 <= day <= prices.size()
         *  profits[trans, 0] = 0; // 0 <= trans <= k
         *
         *  And the iteration logic as below:
         *
         *  profits[trans, day] = max (
         *                              profits[trans, day-1], // same times transactions, but one days before.
         *                              profits[trans-1, i-1] + (prices[day] - prices[i]) // for all of (0 <= i < day )
         *                                                                                // this means find max profit from
         *                                                                                // previous any of days
         *                            )
         *
         */

        int maxProfit(int k, vector<int> &prices) {
            int ndays = prices.size();

            // error case
            if (ndays<=1) return 0;

            // Edge case
            // ---------
            // if the number of transactions is too many, it means we can make
            // as many transactions as we can, that brings us the problem back to
            // Best-Time-To-Buy-And-Sell-Stock-II which can be simply solve in O(n)
            // by using a greedy approach.
            if(k > ndays/2){
                int sum = 0;
                for (int i=1; i<ndays; i++) {
                    sum += max(prices[i] - prices[i-1], 0);
                }
                return sum;
            }

            return maxProfit_DP03(k, prices);//8ms
            return maxProfit_DP02(k, prices);//8ms
            return maxProfit_DP01(k, prices);//492ms
        }


        //DP solution - O(kn^2) complexity
        int maxProfit_DP01 (int k, vector<int> &prices) {
            int ndays = prices.size();
            vector< vector<int> > profits(k+1, vector<int>( ndays+1, 0));
            for(int trans=1; trans<=k; trans++) {
                for (int day=1; day<=ndays; day++) {
                    int m=0;
                    for (int i=1; i<=day; i++) {
                        m = max(m, profits[trans-1][i-1]+ prices[day-1] - prices[i-1]);
                    }
                    profits[trans][day] =  max( profits[trans][day-1], m);
                }
            }
            return profits[k][ndays];
        }

        //DP solution - O(kn) complexity
        //Actually, we could save the loop in above- for(int i=1; i<=day; i++)
        //Becasue there are so many dupliations

        int maxProfit_DP02 (int k, vector<int> &prices) {

            int ndays = prices.size();

            vector< vector<int> > profits(k+1, vector<int>( ndays+1, 0));
            vector<int> m(ndays+1, 0); // tracking the max profits of previous days

            for(int trans=1; trans<=k; trans++) {
                m[0] = profits[trans-1][0] - prices[0];
                for (int day=1; day<=ndays; day++) {
                    profits[trans][day] =  max( profits[trans][day-1], m[day-1]+prices[day-1]);
                    if (day < ndays) {
                        m[day] = max(m[day-1], profits[trans-1][day] - prices[day]);
                    }
                }
            }
            return profits[k][ndays];
        }


        // save the memory, remove the m[ ] array
        int maxProfit_DP03 (int k, vector<int> &prices) {
            int ndays = prices.size();
            vector< vector<int> > profits(k+1, vector<int>( ndays+1, 0));

            for(int trans=1; trans<=k; trans++) {
                int m = profits[trans-1][0] - prices[0];
                for (int day=1; day <= ndays; day++) {
                    profits[trans][day] = max(profits[trans][day-1], m + prices[day-1]);
                    if ( day < ndays ) {
                        m = max(m, profits[trans-1][day] - prices[day]);
                    }
                }
            }

            return profits[k][ndays];
        }
};

#include <iostream>
#include <vector>

using namespace std;

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

private:
    int **dp;  // dp[i][j], start from day[i],
               // the most profit to complete at most j transactions.

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

        if(k >= prices.size()/2)
            return maxProfit(prices);

        dp = new int*[prices.size()];
        for(int i = 0 ; i < prices.size() ; i ++){
            dp[i] = new int[k+1];
            for(int j = 0 ; j <= k ; j ++)
                dp[i][j] = -1;
        }

        int res = solve(prices, 0, k);

        for(int i = 0 ; i < prices.size() ; i ++)
            delete[] dp[i];
        delete[] dp;

        return res;
    }

private:
    int solve(const vector<int>& prices, int startIndex, int left){

        if(startIndex >= prices.size() || left == 0)
            return 0;

        if(dp[startIndex][left] != -1)
            return dp[startIndex][left];

        int minPrice = prices[startIndex];
        int best = 0;
        for(int i = startIndex + 1 ; i < prices.size() ; i ++)
            if(prices[i] > minPrice)
                best = max(best, prices[i] - minPrice + solve(prices, i + 1, left - 1));
            else{
                best = max(best, solve(prices, i + 1, left-1));
                minPrice = prices[i];
            }

        return dp[startIndex][left] = best;
    }

    int maxProfit(const vector<int>& prices){
        int res = 0;
        for(int i = 1 ; i < prices.size() ; i ++)
            if(prices[i] > prices[i-1])
                res += (prices[i] - prices[i-1]);
        return res;
    }
};

int main() {

    int prices1[] = {1, 2};
    int k1 = 1;
    vector<int> pricesVec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
    cout << Solution().maxProfit(k1, pricesVec1) << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n*n*k)
/// Space Complexity: O(n*k)
class Solution {

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

        if(k >= prices.size()/2)
            return maxProfit(prices);

        // dp[i][j], start from day[i],
        // the most profit to complete at most j transactions.
        vector<vector<int>> dp(prices.size()+1, vector<int>(k+1, 0));

        for(int j = 1 ; j <= k ; j ++){

            for(int i1 = prices.size()-2 ; i1 >= 0 ; i1 --){
                dp[i1][j] = dp[i1][j-1];
                for(int i2 = i1 + 1 ; i2 < prices.size() ; i2 ++){
                    if(prices[i2] - prices[i1] > 0)
                        dp[i1][j] = max(dp[i1][j],
                                        prices[i2] - prices[i1] + dp[i2+1][j-1]);
                    dp[i1][j] = max(dp[i1][j], dp[i2][j]);
                }
            }
        }

        return dp[0][k];
    }

private:
    int maxProfit(const vector<int>& prices){
        int res = 0;
        for(int i = 1 ; i < prices.size() ; i ++)
            if(prices[i] > prices[i-1])
                res += (prices[i] - prices[i-1]);
        return res;
    }
};

int main() {

    int prices1[] = {3, 2, 6, 5, 0, 3};
    int k1 = 2;
    vector<int> pricesVec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
    cout << Solution().maxProfit(k1, pricesVec1) << endl;
    // 7

    int prices2[] = {2, 1, 4, 5, 2, 9, 7};
    int k2 = 2;
    vector<int> pricesVec2(prices2, prices2 + sizeof(prices2)/sizeof(int));
    cout << Solution().maxProfit(k2, pricesVec2) << endl;
    // 11

    return 0;
}

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

#include <iostream>
#include <vector>

using namespace std;

/// Using hold and cash
/// Time Complexity: O(n*k)
/// Space Complexity: O(2*k)
class Solution {

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

        if(k >= prices.size()/2)
            return maxProfit(prices);

        if(k <= 0)
            return 0;

        vector<int> hold(k+1, INT_MIN);
        vector<int> cash(k+1, 0);

        for(int price: prices)
            for(int j = k ; j >= 1 ; j --){
                cash[j] = max(cash[j], hold[j] + price);
                hold[j] = max(hold[j], cash[j-1] - price);
            }

        return cash.back();
    }

private:
    int maxProfit(const vector<int>& prices){
        int res = 0;
        for(int i = 1 ; i < prices.size() ; i ++)
            if(prices[i] > prices[i-1])
                res += (prices[i] - prices[i-1]);
        return res;
    }
};

int main() {

    int prices1[] = {3, 2, 6, 5, 0, 3};
    int k1 = 2;
    vector<int> pricesVec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
    cout << Solution().maxProfit(k1, pricesVec1) << endl;
    // 7

    int prices2[] = {2, 1, 4, 5, 2, 9, 7};
    int k2 = 2;
    vector<int> pricesVec2(prices2, prices2 + sizeof(prices2)/sizeof(int));
    cout << Solution().maxProfit(k2, pricesVec2) << endl;
    // 11

    return 0;
}