Best Time to Buy and Sell Stock IV

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(int k, vector<int> &prices) {
        // write your code here
        // cannot buy, profit 0
        if (prices.size() < 1 || k < 1) {
            return 0;
        }
        // times of buy cover the every possible profit
        if (k >= prices.size() / 2) {
            int profits = 0;
            for (int i = 1; i < prices.size(); ++i) {
                profits += max(prices[i] - prices[i-1], 0);
            }
            return profits;
        }
        // normal condition
        int len = prices.size();
        // -------------------------------------------------------------------
        // // Version 1
        // // @param mustsell : i must sell, j times trade 
        // // @param fullbest : i may not sell, j times trade
        vector<vector<int>> mustsell(len + 1, vector<int>(k + 1, 0));
        vector<vector<int>> fullbest(len + 1, vector<int>(k + 1, 0));
        // process
        for (int i = 1; i < len; ++i) {
            int acquire = prices[i] - prices[i-1];
            for (int j = 1; j < k + 1; ++j) {
                // max of 
                // 1. fullbest : prev day, j-1 times best + this day acquire
                // 2. mustsell : prev day has sold + this day acquire
                mustsell[i][j] = max(fullbest[i-1][j-1] + acquire, 
                                    mustsell[i-1][j] + acquire);
                // max of
                // 1. fullbest : prev day, j times trade 
                // 2. mustseel : today must sell, j times trade
                fullbest[i][j] = max(fullbest[i-1][j], mustsell[i][j]);
            }
        }
        return fullbest[len-1][k];
        // -------------------------------------------------------------------
        // Version 2, consider the result only relies on today and prev day
        // 
        vector<int> local(k + 1, 0);
        vector<int> global(k + 1, 0);
        for (int i = 1; i < len; ++i) {
            int ins = prices[i] - prices[i-1];
            for (int j = k; j >= 1; --j) {
                local[j] = max(global[j-1] + max(ins, 0), local[j] + ins);
                global[j] = max(global[j], local[j]);
            }
        }
        for (int i = 1; i <= k; ++i) {
            cout << local[i] << " ";
        }
        cout << endl;
        for (int i = 1; i <= k; ++i) {
            cout << global[i] << " ";
        }
        cout << endl;
        return global[k];
    }
};

Similar problems

x

Tags

x