LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，记录第 i 天结束时状态为持仓、空仓（非冷冻期）、冷冻期能获得的最大收益。持仓的前一天结束状态只能是持仓或空仓，不能是冷冻期，因为冷冻期的后一天不能买入。空仓的前一天结束状态只能是空仓或冷冻期，不能是持仓，否则当天必须卖出，结束状态是冷冻期。冷冻期的前一天状态必须是持仓，并且当天必须卖出

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int sz = size(prices);
    if (sz < 2) {
      return 0;
    }
    vector<int> hold(sz);  // 持仓
    vector<int> sold(sz);  // 空仓
    vector<int> cool(sz);  // 冷冻期
    hold[0] = -prices[0];
    for (int i = 1; i < sz; ++i) {
      hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]);
      sold[i] = max(cool[i - 1], sold[i - 1]);
      cool[i] = hold[i - 1] + prices[i];
    }
    return max(cool[sz - 1], sold[sz - 1]);
  }
};