// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
// prices = [3, 3, 5, 0, 0, 3, 1, 4]
// prices = [1, 2, 3, 4, 5]
// prices = [7, 6, 4, 3, 1]
// prices = [1]
// prices = [1, 2]
// prices = [6, 1, 3, 2, 4, 7]
prices = [1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9]
recOpt(prices, prices.length - 1, 1)
dpOpt(prices)
dpOptAnyDealCnt(prices, 1)
function dpOptAnyDealCnt(arr, dealCnt) {
if (arr.length <= 0 || dealCnt === 0) {
return 0;
}
let L = dealCnt * 2 - 1; // 买入位置，卖出位置 交替
let buySell2d = Array.from({ length: L }, (v, i) =>
Array(arr.length).fill(0)
);
let opt2d = Array.from({ length: dealCnt }, (v, i) =>
Array(arr.length).fill(0)
);
let prev = buySell2d[0]; // 单次交易买入位置
let minPos = 0;
for (let i = 1; i < arr.length; i++) {
let vEnd = arr[i];
let min = arr[minPos];
prev[i] = min < vEnd ? prev[i - 1] : i; // 假设 i 是卖出位置，从哪个位置买入
minPos = vEnd < min ? i : minPos;
for (let j = 0; j < L; ++j) {
let dealNo = Math.floor(j / 2); // 1 -> 0, 2 -> 1, 3 -> 1, 4 -> 2
let isSell = j % 2 === 1;
if (isSell) {
let buy = buySell2d[j - 1];
let sell = buySell2d[j];
let a =
Math.max(0, vEnd - arr[buy[i]]) +
(dealNo === 0 || buy[i] === 0 ? 0 : opt2d[dealNo - 1][buy[i] - 1]); // 从 i 卖出
let b = opt2d[dealNo][i - 1]; // 不从 i 卖出
opt2d[dealNo][i] = Math.max(a, b);
sell[i] = a < b ? sell[i - 1] : i;
} else {
let buy = buySell2d[j];
let a = dealNo === 0 ? 0 : opt2d[dealNo - 1][i - 1]; // 从 i 二次买入（相当于放弃第二次交易机会），所以从 sell[i - 1] 首次卖出
let b =
Math.max(0, vEnd - arr[buy[i - 1]]) +
(dealNo === 0 || buy[i - 1] === 0
? 0
: opt2d[dealNo - 1][buy[i - 1] - 1]); // 不从 i 二次买入
opt2d[dealNo][i] = Math.max(a, b);
buy[i] = a < b ? buy[i - 1] : i;
}
}
}
return _.max(opt2d[dealCnt - 1]);
}
// 2023-10-05 17:00
function dpOpt(arr) {
if (arr.length <= 0) {
return 0;
}
let prev = Array(arr.length).fill(0); // 单次交易买入位置
let sell = Array(arr.length).fill(0); // 单次交易卖出位置
let prev2 = Array(arr.length).fill(0); // 二次买入位置
let minPos = 0,
opt = 0;
for (let i = 1; i < arr.length; i++) {
let vEnd = arr[i];
let min = arr[minPos];
prev[i] = min < vEnd ? prev[i - 1] : i; // 假设 i 是卖出位置，从哪个位置买入
minPos = vEnd < min ? i : minPos;
let a = Math.max(0, vEnd - arr[prev[i]]); // 从 i 卖出
let b = arr[sell[i - 1]] - arr[prev[sell[i - 1]]]; // 不从 i 卖出
sell[i] = a < b ? sell[i - 1] : i;
let A = arr[sell[i - 1]] - arr[prev[sell[i - 1]]]; // 从 i 二次买入（相当于放弃第二次交易机会），所以从 sell[i - 1] 首次卖出
let B =
Math.max(0, vEnd - arr[prev2[i - 1]]) +
(prev2[i - 1] === 0
? 0
: arr[sell[prev2[i - 1] - 1]] - arr[prev[sell[prev2[i - 1] - 1]]]); // 不从 i 二次买入
prev2[i] = A < B ? prev2[i - 1] : i;
opt = Math.max(opt, A, B);
}
return opt;
}
function recOpt(arr, i, dealCnt) {
if (i <= 0 || dealCnt <= 0) {
return 0;
}
const vEnd = arr[i];
function recOptSubArr(arr, i) {
if (i < 0) {
return 0;
}
// 选取买入点
const a = Math.max(vEnd - arr[i], 0) + recOpt(arr, i - 1, dealCnt - 1);
const b = recOptSubArr(arr, i - 1);
return Math.max(a, b);
}
// 选取卖出点
const a = recOptSubArr(arr, i - 1);
const b = recOpt(arr, i - 1, dealCnt);
return Math.max(a, b);
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.