国内可以做网页的网站电商运营培训大概多少学费

网址：https://leetcode.com/problems/Best-Time-to-Buy-and-Sell-Stock/

第一想法是滑动窗口法，稍微尝试后发现不可行，至少我不会。。。

而后想到动态规划，进一步思考发现完全可行：

index	0	1	2	3	4	5
price[]	7	1	5	3	6	4
dp[]	0	0	4	2	5	3
price[index-1] - dp[index-1]	0	0	1	1	1	1

状态：dp[i] 表示prices[]从 0 到 i 这部分的最大利润

状态转移方程：

dp[i] = max(0, prices[i] - (prices[i-1] - dp[i-1]));

使用dp数组的代码如下：

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

然而，dp数组会占用多余的空间。我们知道，一位dp问题的dp数组的赋值往往可以转化为几个变量之间的循环赋值的过程

所以，改进如下：

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size() == 0){return 0;}int ans = 0;int res = 0;int pre_price = prices[0];int pre_dp = 0;for(int price : prices){res = max(0, price - (pre_price - pre_dp));pre_dp = res;pre_price = price;ans = max(res, ans);}return ans;}
};

注意，用这种方式要先判断size是否为0，否则会出现Runtime Error。。。

两份代码的Runtime都是8ms，而改进后内存占用由9.7MB减少到9.5MB，千万别小看这0.2MB。

我们从击败5%的同学升级到击败46%的同学！