My 8ms DP solution with data preprocessing

• 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();
}

}
};``````

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