写了一个单数组的JS实现来,空间优化为O(n)。思路是观察到DP状态转移的两个函数并不会覆盖到需要使用的前一天的值,所以单个数组就足够应付了。
```
var maxProfit = function(k, prices) {
if (k <= 0 || !prices || prices.length <= 1) {
return 0;
}
const MIN = Number.NEGATIVE_INFINITY;
// mp[0...k -> # of transaction][0 -> no stock, 1 -> has stock]
const mp = [
[0, MIN],
[0, -prices[0]],
];
for (let i = 1; i < prices.length; i++) {
const maxK = Math.min(k, Math.floor(i / 2) + 1);
for (let j = 1; j <= maxK; j++) {
if (j >= mp.length) {
// new transaction for the day, must be buy
mp[j] = [MIN, mp[j - 1][0] - prices[i]];
// each day can only add one more transaction, so we are done
break;
}
// This DP function won't accidentally overwrite needed values from
// previous day, so a single array is enough
mp[j][0] = Math.max(mp[j][0], mp[j][1] + prices[i]);
mp[j][1] = Math.max(mp[j][1], mp[j - 1][0] - prices[i]);
}
}
let max = MIN;
for (let j = 0; j < mp.length; j++) {
if (mp[j][0] > max) {
max = mp[j][0];
}
}
return max;
};
```
展开