买卖股票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;}
};