剑指 Offer 63 股票的最大利润

概述

https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

动态规划解

dp[i][j] 表示在第 i 天的利润，j = 0 代表未持有，j = 1 表示持有。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), {0, 0});
        dp[0][1] = - prices[0];
        for (int i = 1; i < prices.size(); i ++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[prices.size() - 1][0];
    }
};

WA 了。

淦，好好读题目行不行，我们只能买一次的。

贪心解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int pin = INT_MAX;
        int p = 0;
        for (int i = 0; i < prices.size(); i ++) {
            if (prices[i] < pin) {
                pin = prices[i];
            } else {
                p = max(p, prices[i] - pin);
            }
        }
        return p;
    }
};

Links: sword-offer-63

未经允许，禁止转载，本文源站链接：https://iamazing.cn/