• 欢迎光临~

121.best-time-to-buy-and-sell-stock 买卖股票的最佳时机

开发技术 开发技术 2022-10-14 次浏览

问题描述

121.买卖股票的最佳时机

解题思路

动态规划

dp[i]表示前i天的最大收益,那么dp[i]的递推公式为:dp[i] = min(dp[i - 1], a[i - 1] - min(price[0, i - 1)), 0)

贪心算法

利用cur记录最小元素,碰到更小的就替换cur的值,遇到比它大的就进行一次利润计算,保存最大的利润。

代码

class Solution {
  private:
    int min(int a, int b) {
        return a < b ? a : b;
    }
    int max(int a, int b, int c) {
        if (a > b)
            return a > c ? a : c;
        else
            return b > c ? b : c;
    }

  public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 1)
            return 0;
        vector<int> min_arr(prices.size() + 1, prices[0]);
        min_arr[0] = prices[0];
        for (int i = 1; i <= prices.size(); i++) {
            min_arr[i] = min(min_arr[i - 1], prices[i - 1]);
        }
        vector<int> dp(prices.size() + 1, 0);
        for (int i = 1; i <= prices.size(); i++) {
            dp[i] = max(dp[i - 1], prices[i - 1] - min_arr[i - 1], 0);
        }
        return dp[prices.size()];
    }
};
程序员灯塔
转载请注明原文链接:121.best-time-to-buy-and-sell-stock 买卖股票的最佳时机
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com