---

[!info] related notes 算法面试题型 MOC 动态规划

Max Asset with Limited Shares

给定价格序列 a[i]，初始现金 m，每天可以选择：

• 不操作
• 买入 1 股（现金 >= price）
• 卖出 1 股（持股 > 0）

目标：第 n-1 天收盘时（按最后一天价格估值持仓），最大化总资产。

状态定义

• dp[h] = 当前天结束时，持有 h 股时的最大现金

每天从 prev 转移到 curr。

JavaScript Snippet

function maxAsset(n, m, a) {
  let prev = new Map();
  prev.set(0, m);

  for (let i = 0; i < n; i++) {
    const price = a[i];
    const curr = new Map();

    for (const [h, c] of prev) {
      // do nothing
      if (!curr.has(h) || c > curr.get(h)) curr.set(h, c);

      // buy 1
      if (c >= price) {
        const nh = h + 1;
        const nc = c - price;
        if (!curr.has(nh) || nc > curr.get(nh)) curr.set(nh, nc);
      }

      // sell 1
      if (h > 0) {
        const nh = h - 1;
        const nc = c + price;
        if (!curr.has(nh) || nc > curr.get(nh)) curr.set(nh, nc);
      }
    }

    prev = curr;
  }

  const lastPrice = a[n - 1];
  let ans = 0;
  for (const [h, c] of prev) {
    ans = Math.max(ans, h * lastPrice + c);
  }
  return ans;
}

Notes

• 状态空间大小与最大可能持股数相关（由资金/价格决定）。
• 这是一个“离散持仓 + 交易步长固定”的 DP 模型。