买卖股票的最佳时机 leetcode121 动态规划

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

暴力做法:

​ $O\left(n^2\right)$O(n2)选取一对数 $num\left[i\right]\left(买入\right),num\left[j\right]\left(卖出\right)$num[i](买入), num[j](卖出),

​ $取max\left(num\right[j]-num[i\left]\right)即可$取max(num[j]−num[i])即可

for(int i=1; i<=n; i++)
  for(int k=i+1; k<=n; k++)
    ans = max(ans, num[j]-num[i]);

动态规划做法:
推荐花花酱的B站讲题视频:
https://www.bilibili.com/video/BV1oW411C7UB



状态表示:

​ $minx\left[i\right]表示第i天买入的最低价格$minx[i]表示第i天买入的最低价格

​ $dp\left[i\right]第i天的最大收益$dp[i]第i天的最大收益

转移方程:

​ $dp\left[i\right]=max\left(dp\right[i-1],num[i]-minx[i-1\left]\right)$dp[i]=max(dp[i−1],num[i]−minx[i−1])

​ $这一天的最优收益=max(前一天的最优,今天卖出价格-今天以前最便宜的买入价格)$这一天的最优收益=max(前一天的最优,今天卖出价格−今天以前最便宜的买入价格)

初始状态:

​ $第一天的最优收益为0,dp\left[1\right]=0$第一天的最优收益为0,dp[1]=0

class Solution {
public:
    int maxProfit(vector<int>& a) {
        int n = a.size(), ans = 0;
        a.insert(a.begin(), 0);

        vector<int> minx(a.size()+1, 0x7f7f7f7f);
        vector<int> dp(a.size()+1, 0);

        for(int i=1; i<=n; i++) //这里可以压缩成O(1)
            minx[i] = min(minx[i-1], a[i]);
        for(int i=2; i<=n; i++)
            dp[i] = max(dp[i-1], a[i]-minx[i-1]);
        return dp[n];

    }
};