代码随想录Day41_DP_stockB

买卖股票1

给定时间序列中一次买入

给定一个股票i天内的价格走势。

暴力解法

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

超时警告。

贪心解法

取差值最小，并且最大值在最小值的右面。

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

暴力的时间复杂度：n*n
贪心的时间复杂度：n

动态规划

DP数组：i天时间间隔中所能获得的最大利润；

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

奇奇怪怪，也许看完第三例会好一点。

买卖股票的最佳时机2

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