京东企业的电子网站建设,武威做网站,四川建设人才网网站,注册公司100万意味着什么描述#xff1a; 给一些列数字#xff0c;表示每条股票的价格#xff0c;如果可以买卖一次#xff08;不能同一天买和卖#xff09;#xff0c;求最大利益#xff08;即差最大#xff09;。 其他三道问题是#xff0c;如果能买卖无限次#xff0c;买卖两次#xff0…描述 给一些列数字表示每条股票的价格如果可以买卖一次不能同一天买和卖求最大利益即差最大。 其他三道问题是如果能买卖无限次买卖两次买卖k次。 题一 实质是求后面一个数减前一个数的最大差值。 维护一个最小值和当前最大值。只需遍历一次空间也是常数。 int maxProfit(vectorint 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(vectorint 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(vectorint 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(vectorint prices) {int n prices.size();if(n0) return 0;int sell1 0, sell2 0, buy1 INT_MIN, buy2 INT_MIN;for(int i 0; in; 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, vectorint prices) { if (prices.size() 2) return 0; int days prices.size(); if (k days) return maxProfit2(prices);auto local vectorvectorint (days, vectorint(k 1));auto global vectorvectorint (days, vectorint(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(vectorint 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, vectorint prices) {int n prices.size();if(kn/2){int buy INT_MIN, sell 0;for(int i0; in; i){buy max(buy, sell-prices[i]);sell max(sell, buyprices[i]);}return sell;}vectorint sell(k1, 0);vectorint buy(k1, 0);for(int i0; ik; i) buy[i] INT_MIN;for(int i0; in; i){for(int j1; jk1; j){buy[j] max(buy[j], sell[j-1]-prices[i]);sell[j] max(sell[j], buy[j]prices[i]);}}return sell[k];
} 转载于:https://www.cnblogs.com/willaty/p/8304914.html
