在股市的交易日中,假设最多可进行两次买卖(即买和卖的次数均小于等于 2 ),规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列,请写一个程序计算一天可以获得的最大收益。请采用时间复杂度低的方法实现。
给定价格序列 prices 及它的长度 n ,请返回最大收益。
数据范围: ,
在股市的交易日中,假设最多可进行两次买卖(即买和卖的次数均小于等于 2 ),规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列,请写一个程序计算一天可以获得的最大收益。请采用时间复杂度低的方法实现。
[10,22,5,75,65,80],6
87
如果只能买卖一次相信大家都会做
用左l 右r 两个下标滑动可以在O(n)时间内完成
见函数Once 不多解释了
但是要购买两次 这就有点麻烦 不过题目说了必须两次分开 所以必须是买卖买卖的顺序 这样就可以用二分的思想
将区间分为长度大于2的左右两个区间 共n-3总分法 每一种分法两边区间各调用一次Once函数然后求和即可
class Stock { public: int Once(vector<int> Prices, int left, int right){ int l = left, r = left + 1; int ans = 0; while(r <= right){ if(Prices[r] > Prices[l]) ans = max(ans, Prices[r] - Prices[l]); else l = r; r++; } return ans; } int maxProfit(vector<int> prices, int n) { int max_ans = Once(prices, 0, n-1); if(n >= 4){ for(int i = 1; i <= n - 3; i++){ int tmp = Once(prices, 0, i) + Once(prices, i+1, n-1); max_ans = max(tmp, max_ans); } } return max_ans; } };
import java.util.*; public class Stock { //分别得出以i点为分割点,左半段最大收益的数组left,和右半段最大收益的数组right后. //我们就可以遍历一遍这两个数组,找出最大的left+right组合。 public int maxProfit(int[] prices, int n) { if (n==0){ return 0; } int[] left = new int[n]; int[] right= new int[n]; int leftMin=prices[0]; int rightMax=prices[n-1]; int sum = 0; //prices[0]到prices[i]的最大收益应该: // 当前卖出能获得的最大收益 和 prices[0]到prices[i-1]的最大收益中 // 二者较大的那个。 for(int i = 1 ; i<n ; i++){ leftMin = Math.min(prices[i],leftMin); left[i] = Math.max(prices[i]-leftMin , left[i-1]); } for(int i = n-2 ; i>=0 ;i--){ rightMax = Math.max(prices[i],rightMax); right[i] = Math.max(rightMax-prices[i] , right[i+1]); } for(int i = 0 ;i<n ;i++){ if((left[i]+right[i])>sum) sum = left[i]+right[i]; } return sum; } }
//time complexiy O(n), space complexity O(n) public class Stock { public int maxProfit(int[] prices, int n) { // write code here if (n == 0) { return 0; } //from left to right int[] profitBefore = new int[n]; int buyMin = prices[0]; profitBefore[0] = 0; for (int i = 1; i < n; i++) { buyMin = Math.min(buyMin, prices[i]); profitBefore[i] = Math.max(profitBefore[i - 1], prices[i] - buyMin); } //from right to left int[] profitAfter = new int[n]; int sellMax = prices[n - 1]; profitAfter[n - 1] = 0; for (int i = n - 2; i >= 0; i--) { sellMax = Math.max(sellMax, prices[i]); profitAfter[i] = Math.max(profitAfter[i + 1], sellMax - prices[i]); } //combine int max = 0; for (int i = 0; i < n - 1; i++) { max = Math.max(max, profitBefore[i] + profitAfter[i]); } return max; } }
public int maxProfit(int[] prices, int n) { //第i天之前的最大收益 int[] preMaxProfit = new int[n]; //第i天之后的最大收益 int[] postMaxProfit = new int[n]; //总的最大收益 int maxProfit = Integer.MIN_VALUE; //如果今天的价格减掉最小价格比截止到昨天的最大收益大, //就用今天的价格减去最小的价格;否则,用截止到昨天的最大收益 int minBuy = prices[0]; for(int i=1;i<n;i++){ minBuy = Math.min(minBuy, prices[i]); preMaxProfit[i] = Math.max(preMaxProfit[i-1], prices[i] - minBuy); } //如果最大价格减掉今天价格比明天以后买入的最大收益大, //就用最大价格减掉今天的价格;否则,用明天以后买入的最大收益 int maxSell = prices[n-1]; for(int i=n-2;i>=0;i--){ maxSell = Math.max(maxSell, prices[i]); postMaxProfit[i] = Math.max(postMaxProfit[i+1], maxSell - prices[i]); } //总的最大利润 for(int i=0;i<n;i++){ maxProfit = Math.max(maxProfit, preMaxProfit[i]+postMaxProfit[i]); } return maxProfit; }
import java.util.*; public class Stock { public int[] getMax(int[] dis, int n) { int[] dp = new int[n]; int max = Integer.MIN_VALUE; int current = 0; for (int i = 0; i < dis.length; ++i) { current += dis[i]; current = Math.max(current, dis[i]); max = Math.max(current, max); dp[i] = max; } return dp; } public int[] getMin(int[] dis, int n) { int[] dp = new int[n]; int min = Integer.MAX_VALUE; int current = 0; for (int i = dis.length - 1; i >= 0; --i) { current += dis[i]; current = Math.min(current, dis[i]); min = Math.min(current, min); dp[i] = min; } return dp; } public int maxProfit(int[] prices, int n) { // write code here int[] dis = new int[prices.length]; int[] dis2 = new int[prices.length]; for (int i = 1; i < dis.length; ++i) { dis[i] = prices[i] - prices[i - 1]; } for (int i = dis.length - 2; i >= 0; --i) { dis2[i] = prices[i] - prices[i + 1]; } int[] max = getMax(dis, n); int[] min = getMin(dis2, n); int result = Integer.MIN_VALUE; for (int i = 0; i < max.length; ++i) { result = Math.max(result, max[i] - min[i]); } return result; } }
import java.util.*; public class Stock { public int maxProfit(int[] prices, int n) { // write code here int[] left = new int[n]; int[] right = new int[n]; int min = prices[0]; int cost = 0; for(int i = 1;i<prices.length;i++){ if(prices[i]-min>cost){ cost = prices[i]-min; } if(prices[i]<min) min = prices[i]; left[i] = cost; } cost = 0; int max = prices[n-1]; for(int i = n-1;i>=0;i--){ if(max-prices[i]>cost){ cost = max-prices[i]; } if(prices[i]>max) max = prices[i]; right[i] = cost; } int r = 0; for(int i = 1;i<n-1;i++) if(left[i]+right[i]>r) r = left[i]+right[i]; return r; } }
class Stock:
def maxProfit(self, prices, n):
if not prices: return 0
left, right = [], []
minLeft, cur = prices[0], 0
for i, v in enumerate(prices):
cur = max(v - minLeft, cur)
left.append(cur)
minLeft = min(minLeft, v)
maxRight, cur = prices[-1], 0
for i, v in enumerate(prices[::-1]):
cur = max(maxRight - v, cur)
right.insert(0, cur)
maxRight = max(maxRight, v)
return max(map(lambda c: left[c] + right[c], range(len(prices))))
class Stock:
def maxProfit(self, prices, n):
buy1, buy2, sell1, sell2 = -999999999, -9999999999, 0, 0
for x in prices:
sell2 = max(sell2, buy2 + x)
buy2 = max(buy2, sell1 - x)
sell1 = max(sell1, buy1 + x)
buy1 = max(buy1, -x)
return sell2
class Stock { public: int maxProfit(vector<int> prices, int n) { if(n==0) return 0; vector<int> profit1(n,0); vector<int> profit2(n,0); int Min = prices[0]; int Max = prices[n-1]; int MaxProfit = 0; for(int i=1;i<n;i++) { Min = min(prices[i], Min); profit1[i] = max(profit1[i-1], prices[i]-Min); } for(int i=n-2;i>=0;i--) { Max = max(prices[i], Max); profit2[i] = max(profit2[i+1], Max-prices[i]); } for(int i=0;i<n;i++) MaxProfit = max(MaxProfit, profit1[i]+profit2[i]); return MaxProfit; } };
public int maxProfit(int[] prices, int n) {
int len = n;
int res = maxProfitHelp(prices, 0, len - 1);
for (int i = 2; i <= len - 2; i++) {
int valLeft = maxProfitHelp(prices, 0, i - 1);
int valRight = maxProfitHelp(prices, i, len - 1);
int val = valLeft + valRight;
if (valLeft > res) res = valLeft;
if (valRight > res) res = valRight;
if (val > res) res = val;
}
return res;
}
private int maxProfitHelp(int[] prices, int left, int right) {
int min = prices[left];
int max = prices[left + 1];
int res = max - min;
if(max < min){
min = max;//十分隐蔽的bug
}
for (int i = left + 2; i <= right; i++) {
if (prices[i] < min) {
min = prices[i];
max = Integer.MIN_VALUE;
} else {
if (prices[i] > max) {
max = prices[i];
res = Math.max(res, max - min);
}
}
}
return res;
}
class Stock { public: int maxProfit(vector<int> prices, int n) { if(n<4) return 0; vector<int> vec(n,0); int min=prices[0]; for(int i=1;i<n;i++){ if(prices[i]-min<=vec[i-1]){ vec[i]=vec[i-1]; }else{ vec[i]=prices[i]-min; } if(prices[i]<min) min=prices[i]; } int max=prices[n-1]; int R=0; for(int i=n-2;i>0;i--){ if(max-prices[i]+vec[i-1]>R) R=max-prices[i]+vec[i-1]; if(prices[i]>max) max=prices[i]; } return R; } };
//DP //forward(n)表示第一次交易第n天卖出最大获利 //backward(n)表示第二次交易第n天买入最大获利 class Stock { public: int maxProfit(vector<int> prices, int n) { // write code here vector<int> forward(n,0); int minV = prices[0]; forward[0]=0; for(int i=1;i<n;i++) { if(prices[i]<minV)minV=prices[i]; forward[i] = max(prices[i]-minV,forward[i-1]); } vector<int>backward(n,0); int maxV = prices[n-1]; backward[n-1]=0; for(int j=n-2;j>=0;j--) { if(prices[j]>maxV)maxV=prices[j]; backward[j] = max(maxV-prices[j],backward[j+1]); } int ans = numeric_limits<int>::min(); for(int i=1;i<n-2;i++) ans = max(forward[i]+backward[i+1],ans); ans = max(max(ans,forward[n-1]),backward[0]); //可能只有一次操作 return ans; } };
class Stock { public: int getMin(vector<int> prices,int begin,int end){ vector<int> dp(end-begin+1); dp[0]=-prices[begin+0]; dp[1]=prices[begin+1]-prices[begin+0]; int pof=dp[1]+prices[begin+1]>0? dp[1]:-prices[begin+1]; int min=prices[begin+0]>prices[begin+1]? prices[begin+1]:prices[begin+0]; for(int i=begin+2;i<=end;i++){ dp[i-begin]=prices[i]-min; if(pof<dp[i-begin]) pof=dp[i-begin]; if(prices[i]<min) min=prices[i]; } return pof; } int maxProfit(vector<int> prices, int n) { /*时间复杂度为O(n*n)*/ int max=getMin(prices,0,n-1); for(int i=1;i<n-2;i++){ int p=getMin(prices,0,i)+getMin(prices,i+1,n-1); if(p>max){ max=p; } } return max; } };
int maxProfit(vector<int> prices, int n) { // write code here int minPrice = prices[0]; vector<int> max_profit1(n, 0); for(int i = 1; i < n; ++i){ max_profit1[i] = std::max(max_profit1[i-1], prices[i]-minPrice); minPrice = std::min(minPrice, prices[i]); } int maxPrice = prices[n-1]; vector<int> max_profit2(n, 0); for(int i = n-2; i >= 0; --i){ max_profit2[i] = std::max(max_profit2[i+1], maxPrice-prices[i]); maxPrice = std::max(maxPrice, prices[i]); } for(int i = 0; i < n; ++i) max_profit1[i] += max_profit2[i]; return *max_element(max_profit1.begin(), max_profit1.end()); }
class Stock { public: int maxProfit(vector<int> prices, int n) { // write code here if (n==0){ return 0; } vector<int> pre_profit(n,0); vector<int> post_profit(n,0); int min_buy = prices[0]; for(int i=1;i<n;i++){ min_buy = min(prices[i], min_buy); pre_profit[i] = max(pre_profit[i-1], prices[i]-min_buy); } int max_sell = prices[n-1]; for(int j=n-2;j>=0;j--){ max_sell = max(prices[j], max_sell); post_profit[j] = max(post_profit[j+1], max_sell-prices[j]); } int max_profit = 0; for(int i=0; i<n;i++){ max_profit = max(max_profit, pre_profit[i] + post_profit[i]); } return max_profit; } };动态规划法 。以第i天为分界线,计算第i天之前进行一次交易的最大收益preProfit[i],和第i天之后进行一次交易的最大收益postProfit[i],最后遍历一遍,max{preProfit[i] + postProfit[i]} (0≤i≤n-1)就是最大收益。
import java.util.*; //已通过测试,发现好多人都不喜欢写注释,喜欢直接粘代码, public class Stock { //简单说一下我的做题思路, //其实我的原始思路是用二分法做,先把数组从中间分开, //然后在两部分中分别找最大差值,然后保存最大差值进行相加 //完事之后,将中间的指针,也就是进行二分的指针向右移或者向左移 //又划分成了两部分,依次找最大差值, //直到最后两个差值之和为最大值,返回最大值。 public int maxProfit(int[] prices, int n) { int temp1 = 0,temp2 = 0 , temp3 = 0, l = 0; //既然从中间划分两部分,之后又要在往前划分和往后划分, //所以直接一开始就从最前面开始划分,将数组划分两部分 while(l<n){ //l变量用来划分数组 //第一个for循环寻找的最大差值,仅限于l变量之前。 for(int i = 0 ; i < l+1 ; i++){ for(int j = i+1 ; j < l+1 ; j++){ if(prices[j]-prices[i]>temp1){ temp1 = prices[j]-prices[i]; } } } //第二个for循环寻找的最大差值,仅限于l变量之后。 for(int i = l+1 ; i < n ; i++){ for(int j = i+1 ; j < n ; j++){ if(prices[j]-prices[i]>temp2){ temp2 = prices[j]-prices[i]; } } } //判断两个变量之和是否是最大差值 if(temp2+temp1>temp3){ temp3 = temp2+temp1 ; } //此处一定要将两个部分的最大差值重新置0; //否则结果会出错。因为它里面存有之前的最大差值 //如果不重置,那么最后在判断的时候会重复计算。 temp2 = 0 ; temp1 = 0; l++; } return temp3; } }
//哈哈,这是我以前做过的题目。。。。复杂度最低的算法:
public static int maxProfit(int[] prices, int n) { int firstBuyProfit=Integer.MIN_VALUE; int firstSaleProfit=Integer.MIN_VALUE; int secondBuyProfit=Integer.MIN_VALUE; int secondSaleProfit=Integer.MIN_VALUE; for (int i = 0; i < n; i++) { firstBuyProfit=Math.max(firstBuyProfit, -prices[i]); firstSaleProfit=Math.max(firstSaleProfit, firstBuyProfit+prices[i]); secondBuyProfit=Math.max(secondBuyProfit, firstSaleProfit-prices[i]); secondSaleProfit=Math.max(secondSaleProfit, secondBuyProfit+prices[i]); } return secondSaleProfit; }