leetCode-Record

leetCode-Record copied to clipboard

典型的dp问题，状态转移方程式为 第i天的最大收益 = max(第i - 1 天的收益,当天的价格 - 之前最小的价格)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices.length === 0) {
        return 0;
    }
   let dp = Array(prices.length).fill(0);
   let sum = prices[0];
   for(let i = 1;i<prices.length;i++) {
       dp[i] = Math.max(prices[i] - sum,dp[i -1]);
       if(sum > prices[i]) {
           sum = prices[i];
       }
   }
   return dp.sort((a,b)=>b-a)[0];
};