29:null 2a:["$","title",null,{"children":"买卖股票的最佳时机3,4 | Bruce He | Observable"}] 2f:T6b8,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]); }30:[] 2d:{"id":"cd0769d30088c5a6","slug":null,"title":"买卖股票的最佳时机3,4","thumbnail":"8a160b1fb41ff71c983856e805787a7600124e97b369ae516c25f256fca00f22","access_level":"public","create_time":"$D2023-09-27T00:55:06.699Z","update_time":"$D2023-10-05T12:04:36.653Z","view_time":null,"first_public_time":"$D2023-09-27T00:55:06.699Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"5e3282f592b2837f","login":"heganjie","name":"Bruce He","avatar_url":"https://avatars-next.observableusercontent.com/58d33228761b95f76b498c59d4664893e0c8b694acb62ff0342f8d22ebafb8e3","tier":"starter_2024"},"version":370,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"8bc3b438d4504c1b","login":"heganjie","name":"Bruce He","avatar_url":"https://avatars-next.observableusercontent.com/58d33228761b95f76b498c59d4664893e0c8b694acb62ff0342f8d22ebafb8e3","tier":null}],"members":[{"type":"individual","id":"8bc3b438d4504c1b","login":"heganjie","name":"Bruce He","avatar_url":"https://avatars-next.observableusercontent.com/58d33228761b95f76b498c59d4664893e0c8b694acb62ff0342f8d22ebafb8e3","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"40d740bf395b0cdf","slug":"untitled","title":"algorithm","owner":{"id":"5e3282f592b2837f","login":"heganjie","name":"Bruce He"}},"type":"notebook","body":{"title":"买卖股票的最佳时机3,4","cells":[{"id":0,"value":"# 买卖股票的最佳时机3,4","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5,"value":"// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/\n// prices = [3, 3, 5, 0, 0, 3, 1, 4]\n// prices = [1, 2, 3, 4, 5]\n// prices = [7, 6, 4, 3, 1]\n// prices = [1]\n// prices = [1, 2]\n// prices = [6, 1, 3, 2, 4, 7]\nprices = [1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"recOpt(prices, prices.length - 1, 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":239,"value":"dpOpt(prices)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":309,"value":"dpOptAnyDealCnt(prices, 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":307,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":174,"value":"// 2023-10-05 17:00\nfunction dpOpt(arr) {\n if (arr.length <= 0) {\n return 0;\n }\n\n let prev = Array(arr.length).fill(0); // 单次交易买入位置\n let sell = Array(arr.length).fill(0); // 单次交易卖出位置\n let prev2 = Array(arr.length).fill(0); // 二次买入位置\n let minPos = 0,\n opt = 0;\n for (let i = 1; i < arr.length; i++) {\n let vEnd = arr[i];\n let min = arr[minPos];\n prev[i] = min < vEnd ? prev[i - 1] : i; // 假设 i 是卖出位置，从哪个位置买入\n minPos = vEnd < min ? i : minPos;\n\n let a = Math.max(0, vEnd - arr[prev[i]]); // 从 i 卖出\n let b = arr[sell[i - 1]] - arr[prev[sell[i - 1]]]; // 不从 i 卖出\n sell[i] = a < b ? sell[i - 1] : i;\n \n let A = arr[sell[i - 1]] - arr[prev[sell[i - 1]]]; // 从 i 二次买入（相当于放弃第二次交易机会），所以从 sell[i - 1] 首次卖出\n let B =\n Math.max(0, vEnd - arr[prev2[i - 1]]) +\n (prev2[i - 1] === 0\n ? 0\n : arr[sell[prev2[i - 1] - 1]] - arr[prev[sell[prev2[i - 1] - 1]]]); // 不从 i 二次买入\n prev2[i] = A < B ? prev2[i - 1] : i;\n opt = Math.max(opt, A, B);\n }\n\n return opt;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6,"value":"function recOpt(arr, i, dealCnt) {\n if (i <= 0 || dealCnt <= 0) {\n return 0;\n }\n const vEnd = arr[i];\n\n function recOptSubArr(arr, i) {\n if (i < 0) {\n return 0;\n }\n // 选取买入点\n const a = Math.max(vEnd - arr[i], 0) + recOpt(arr, i - 1, dealCnt - 1);\n const b = recOptSubArr(arr, i - 1);\n return Math.max(a, b);\n }\n // 选取卖出点\n const a = recOptSubArr(arr, i - 1);\n const b = recOpt(arr, i - 1, dealCnt);\n return Math.max(a, b);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"