My 8ms DP solution with data preprocessing


  • 4
    H

    The test time is similar to other solutions reported. But it has significant advantage when prices size becomes large. The basic idea is to merge daily profit array such as "+ - - - + - + +" into array of pattern "+ - + - + ..." and do normal DP.

    class Solution {
    public:
        // Merge transactions.
        int maxProfit(int k, vector<int>& prices) {
            if(k == 0 || prices.size() < 2) return 0;
            
            // The values in profits should be: + - + -...
            vector<int> profits{0};
            
            for(int i = 1; i < prices.size(); ++i) {
                int diff = prices[i] - prices[i-1];
                if(diff < 0 && profits.front() == 0) continue;
                if(diff * profits.back() >= 0) {
                    profits.back() += diff;
                } else {
                    profits.push_back(diff);
                }
            }
            
            // Number of positive blocks.
            int pos = ceil(profits.size()/2.0);
            if(k >= pos) {
                int sum = 0;
                for(int i = 0; i < profits.size(); ++i) sum += profits[i] >= 0 ? profits[i] : 0;
                return sum;
            } else {
    			vector<int> global(k, 0);
                vector<int> local(k, 0);
    			for (int i = 0; i < pos; ++i) {
    				for (int j = 0, last = 0; j <= i && j < k; ++j) {
                        int tmp = global[j];
                        local[j] = max(last+profits[2*i], i == 0 ? 0 : (local[j] + profits[2 * i] + profits[2 * i - 1]));
                        global[j] = max(local[j], global[j]);
                        last = tmp;
    				}
    			}
    			return global.back();
            }
            
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.