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; }