121.买卖股票的最佳时机 ​

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let res = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      res = Math.max(res, prices[j] - prices[i]);
    }
  }
  return res;
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let res = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      res = Math.max(res, prices[j] - prices[i]);
    }
  }
  return res;
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let low = Number.MAX_VALUE;
  let res = 0;
  for (let i = 0; i < prices.length; i++) {
    // 求左边最小值
    low = Math.min(low, prices[i]);
    // 用当前值 - 前面的最小值 不断求最大
    res = Math.max(res, prices[i] - low);
  }
  return res;
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let low = Number.MAX_VALUE;
  let res = 0;
  for (let i = 0; i < prices.length; i++) {
    // 求左边最小值
    low = Math.min(low, prices[i]);
    // 用当前值 - 前面的最小值 不断求最大
    res = Math.max(res, prices[i] - low);
  }
  return res;
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const dp = Array.from(new Array(prices.length), () => [0, 0]);
  dp[0] = [-prices[0], 0];
  for (let i = 1; i < prices.length; i++) {
    // 当前持有股票 = max(之前一直持有保持现状，今天买入变成了持有)
    dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
    // 当前未持有股票 = max(之前一直未持有保持现状，今天卖掉了变成了未持有)
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  }
  return dp[prices.length - 1][1];
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  const dp = Array.from(new Array(prices.length), () => [0, 0]);
  dp[0] = [-prices[0], 0];
  for (let i = 1; i < prices.length; i++) {
    // 当前持有股票 = max(之前一直持有保持现状，今天买入变成了持有)
    dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
    // 当前未持有股票 = max(之前一直未持有保持现状，今天卖掉了变成了未持有)
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  }
  return dp[prices.length - 1][1];
};