leetcode_121 买卖股票的最佳时期

1. 题意

有一个股价变化图，你可以在一天买入，在未来一天卖出。

求通过这样一次操作的最大获利。

2. 题解

2.1 枚举

直接枚举，买入卖出的时间，肯定会超时啦~

时间复杂度为$O(n^2)$
空间复杂度为$O(1)$

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        
        int ans = 0;

        int n = prices.size();

        for (int i = 0;i < n;++i) {
            for(int j = i + 1;j < n; ++j) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};

2.2 贪心

我们不难想到，我们每次卖股票的时候，只需要买入当前股票之前最低股份的股票就可以了！因此我们可以边统计最低股价，一边计算差值的最大值。

class Solution {
public:
  int maxProfit(vector<int>& prices) {
        
        int n = prices.size();
        int ans = 0;
        int mn = prices[0];

        for (int i = 1; i < n; ++i) {
            ans = max(prices[i] - mn, ans);
            mn  = min(mn, prices[i]);
        }

        return ans;
  }
};

2.3 动态规划

动态规划的思路和贪心的感觉差不多，也不知道这算不算动态规划~

我们用$dp[i]$表示卖出的股票是$prices[i]$时的最大差值。

因此$ans=\max \left\{dp[i]|1\le i\le prices.size()-1\right\}$。

同样对于$dp[i]$，我们需要知道$i$之前的最小股份，所以最终代码跟

贪心差不多？空间优化完后，代码估计就跟贪心一样，就不写了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int n   = prices.size();
        int ans = 0;
        vector<int> dp(n + 1, 0);

        int mn = prices[0];
        for (int i = 0;i < n; ++i) {
            dp[i + 1] = max( dp[i], prices[i] - mn);
            mn = min( prices[i], mn);
        }
        return dp[n];
    }
};

2.4 差分+动态规划

这个题目跟lc53 最大子数组和, 是相互变形的关系。

其实也就是差分和前缀和的关系。

lc53可以通过前缀和转换成这个问题，当然这个问题也可以通过差分变成

最大子数组和。贴个代码吧，也懒得再解释了OvO

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    
        adjacent_difference( prices.begin(), prices.end(), prices.begin());
        
        prices[0] = 0;
        int ans = 0;
        int pre = 0;
        for (auto v: prices) {
            pre += v;
            ans = max( pre, ans);
            if (pre < 0)
                pre = 0;
        }

        return ans;
  }
};