leetcode 121 股票买卖问题系列
描述：
给一些列数字，表示每条股票的价格，如果可以买卖一次（不能同一天买和卖），求最大利益（即差最大）。
其他三道问题是，如果能买卖无限次，买卖两次，买卖k次。
题一：
实质是求后面一个数减前一个数的最大差值。
维护一个最小值，和当前最大值。只需遍历一次，空间也是常数。
int maxProfit(vector<int>& prices) { if (prices.size() < 1) return 0; int min_ = prices[0]; int ret = 0; for (int i = 1; i < prices.size(); i++) { ret = max(ret, prices[i] - min_); min_ = min(min_, prices[i]); } return ret; }
题二：
只要是后一个数比前一个大，都增。
int maxProfit(vector<int>& prices) { if (prices.size() < 1) return 0; int ret = 0; for (int i = 0; i < prices.size() - 1; i++) { ret += max(prices[i + 1] - prices[i], 0); } return ret; }
题三：
可进行两次操作。
其中一个思路，可以关注分界点，可以枚举分界点，求左右两边的最优操作，在LeetCode会超时，显然，复杂度n^2。
思考下优化，我们可以计算每个点的最大值，左边不用重复计算，每次分界点往左移，都像题一那样计算最大值即可；
而右边，其实可以反向计算一遍，但是，右边改成求最小值。
最后加起来即可。
int maxProfit(vector<int>& prices) { int size = prices.size(); if (size < 1) return 0; int* left = new int[size]{0}; int* right = new int[size]{0}; int ret = 0; int lmin = prices[0]; int lmax = 0; for (int i = 1; i < size; i++) { lmax = max(lmax, prices[i] - lmin); left[i] = lmax; lmin = min(lmin, prices[i]); } int rmin = 0; int rmax = prices[size - 1]; for (int i = size - 1; i >= 0; i--) { rmin = min(rmin, prices[i] - rmax); right[i] = -rmin; rmax = max(rmax, prices[i]); } for (int i = 0; i < size - 1; i++) { ret = max(ret, left[i] + right[i + 1]); } return max(ret, left[size - 1]); }
思路二：
int maxProfit(vector<int>& prices) { int n = prices.size(); if(n==0) return 0; int sell1 = 0, sell2 = 0, buy1 = INT_MIN, buy2 = INT_MIN; for(int i =0; i<n; i++) { buy1 = max(buy1, -prices[i]); sell1 = max(sell1, prices[i]+buy1); buy2 = max(buy2, sell1-prices[i]); sell2 = max(sell2, prices[i]+buy2); } return sell2; }
题四：
动态规划：
其中diff表示今天和昨天的差。
global[i][j] = max(local[i][j], global[i-1][j])
local[i][j] = max(global[i-1][j-1] + max(diff,0), local[i-1][j] + diff)
local[i][j]表示最后一次卖出在今天的最大利益，局部最优。
global[i][j]表示全局最优。
第一条式子：要么在今天卖出最优，要么前一天的全局最优。
第二条式子：前者为之前的全局最优加上最后一次交易在今天。
注意diff，我们要的是不大于j的交易次数；
如果i - 1天还持有，则i天卖出，共j - 1次操作；如果i-1天不持有，则i - 1天买入，i天卖出，共j次操作。
后者为i - 1天卖出加上今天diff，表示i - 1天还持有，加上今天的。
int maxProfit(int k, vector<int>& prices) { if (prices.size() < 2) return 0; int days = prices.size(); if (k >= days) return maxProfit2(prices); auto local = vector<vector<int> >(days, vector<int>(k + 1)); auto global = vector<vector<int> >(days, vector<int>(k + 1)); for (int i = 1; i < days ; i++) { int diff = prices[i] - prices[i - 1]; for (int j = 1; j <= k; j++) { local[i][j] = max(global[i - 1][j - 1], local[i - 1][j] + diff); global[i][j] = max(global[i - 1][j], local[i][j]); } } return global[days - 1][k]; } int maxProfit2(vector<int>& prices) { int maxProfit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] > prices[i - 1]) { maxProfit += prices[i] - prices[i - 1]; } } return maxProfit; }
类似题三的做法：
int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(k>n/2) { int buy = INT_MIN, sell = 0; for(int i=0; i<n; i++) { buy = max(buy, sell-prices[i]); sell = max(sell, buy+prices[i]); } return sell; } vector<int> sell(k+1, 0); vector<int> buy(k+1, 0); for(int i=0; i<=k; i++) buy[i] = INT_MIN; for(int i=0; i<n; i++) { for(int j=1; j<k+1; j++) { buy[j] = max(buy[j], sell[j-1]-prices[i]); sell[j] = max(sell[j], buy[j]+prices[i]); } } return sell[k]; }优质内容筛选与推荐>>
1、Vue scrollBehavior 滚动行为
2、ASP.NET中Cookie跨域的问题及解决代码
3、马克
4、课程作业1
5、ubuntu 网络设置