In this Leetcode Best Time to Buy and Sell Stock III problem solution, we have given an array of prices where prices[i] is the price of a given stock on an ith day. Find the maximum profit you can achieve. You may complete at most two transactions.
Problem solution in Python.
l = len(prices)
if l < 2:
return 0
profit = 0
dp1,dp2 = [0]*l,[0]*(l+1)
minval,maxval = prices[0],prices[-1]
for i in xrange (1,l):
if prices[i] < minval:
minval = prices[i]
dp1[i] = dp1[i-1]
else:
dp1[i] = max(dp1[i-1],prices[i]-minval)
for i in xrange (l-1,-1,-1):
if prices[i] > maxval:
maxval = prices[i]
dp2[i] = dp2[i+1]
else:
dp2[i] = max(dp2[i+1],maxval - prices[i])
for i in xrange (l):
profit = max(profit,dp1[i] + dp2[i+1])
return profit
Problem solution in Java.
public int maxProfit(int[] prices) {
int res = 0;
int len = prices.length;
if(len < 2) return 0;
int[] leftmax = new int[len];
int[] rightmax = new int[len];
leftmax[0] = 0;
rightmax[len-1] = 0;
int left = prices[0];
int right = prices[len-1];
for(int i = 1; i < len; i++) {
left = Math.min(left, prices[i]);
leftmax[i] = Math.max(leftmax[i-1], prices[i] - left);
right = Math.max(right, prices[len-1-i]);
rightmax[len-1-i] = Math.max(rightmax[len-i], right - prices[len-1-i]);
}
for(int i = 0; i < len; i++) {
res = Math.max(res, leftmax[i] + rightmax[i]);
}
return res;
}
Problem solution in C++.
class Solution {
public:
int maxProfit(vector<int>& prices) {
int states[2][4] = {INT_MIN, 0, INT_MIN, 0};
int len = prices.size(), i, cur = 0, next =1;
for(i=0; i<len; ++i)
{
states[next][0] = max(states[cur][0], -prices[i]);
states[next][1] = max(states[cur][1], states[cur][0]+prices[i]);
states[next][2] = max(states[cur][2], states[cur][1]-prices[i]);
states[next][3] = max(states[cur][3], states[cur][2]+prices[i]);
swap(next, cur);
}
return max(states[cur][1], states[cur][3]);
}
};
Problem solution in C.
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
int* getLeftMaxProfit(int *prices, int pricesSize){
int *leftP=malloc(pricesSize*sizeof(int));
int maxProfit=0;
int minPrice=prices[0];
leftP[0]=0;
for(int i=1;i<pricesSize;i++){
maxProfit=max(maxProfit,prices[i]-minPrice);
minPrice=min(minPrice,prices[i]);
leftP[i]=maxProfit;
}
return leftP;
}
int* getRightMaxProfit(int *prices, int pricesSize){
int *rightP=malloc(pricesSize*sizeof(int));
int maxProfit=0;
int maxPrice=prices[pricesSize-1];
rightP[pricesSize-1]=0;
for(int i=pricesSize-2;i>=0; i--){
maxProfit=max(maxProfit, maxPrice-prices[i]);
maxPrice=max(maxPrice, prices[i]);
rightP[i]=maxProfit;
}
return rightP;
}
int maxProfit(int* prices, int pricesSize){
int *leftP;
int *rightP;
leftP=getLeftMaxProfit(prices, pricesSize);
rightP=getRightMaxProfit(prices, pricesSize);
int maxProfit=0;
for(int i=0;i<pricesSize-1;i++){
maxProfit=max(maxProfit,leftP[i]+rightP[i+1]);
}
maxProfit=max(maxProfit,leftP[pricesSize-1]);
maxProfit=max(maxProfit,rightP[0]);
return maxProfit;
}