題目地址： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
題目描述： 給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格杖刷。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。
返回你可以從這筆交易中獲取的最大利潤(rùn)企量。如果你不能獲取任何利潤(rùn)查排，返回 0 。
參考代碼：
class Solution {
public:
//貪心
int maxProfit(vector<int>& prices) {
int result = 0;
int minVaule = INT_MAX;
for (int i = 0; i<prices.size(); i++) {
minVaule = min(minVaule, prices[i]);
if (i > 0) {
result = max(result, prices[i] - minVaule);
}
}
return result;
}
//動(dòng)態(tài)
int maxProfit1(vector<int>& prices) {
int result = 0;
if (prices.size() == 0) {
return result;
}
//dp[i][0] 第i天 持有股票 dp[i][1] 第i天 不持有
// 狀態(tài)遷移
vector<vector<int>> dp = vector<vector<int>> (prices.size(),vector<int>(2,0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i<prices.size();i++) {
dp[i][0] = max(dp[i-1][0],-prices[i]);// 只能買一次
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]); // 可以買多次
dp[i][1] = max(dp[i-1][1],prices[i] + dp[i-1][0]);
}
return dp[prices.size()-1][1];
}
};
