大连做企业网站的公司国内新闻大事20条简短

剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode）

类似题：LeetCode第 121 题：买股票的最佳时机(C++)_zj-CSDN博客

o(n^2)的dp，思路很直接，但是最后一个测试用例超时了：

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

可以使用一个变量随时记录前i天的最小=价格：

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.empty())  return 0;vector<int> dp(prices.size(), 0);int min_price = prices[0];//记录前i天的最小价格for(int i = 1; i < prices.size(); ++i){//卖或者不卖dp[i] = max(dp[i-1], prices[i] - min_price);min_price = min(min_price, prices[i]);//更新最小价格}return *max_element(dp.begin(), dp.end());}
};

状态压缩也很简单，就不写了。

当然也可以不使用dp:

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.empty())  return 0;int res = 0, min_price = prices[0];//记录前i天的最小价格for(int i = 1; i < prices.size(); ++i){if(prices[i] < prices[i-1]) min_price = min(prices[i], min_price);//更新最小价格else res = max(res, prices[i] - min_price);}return res;}
};