剑指 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