Best Time to Buy and Sell Stock III

Question

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Analysis

``````// Assume we are in state S
// If we buy, we are spending money but we can also choose to do nothing
// Doing nothing means going from S->S
// Buying means going from some state X->S, losing some money in the process
S = max(S, X-prices[i])

// Similarly, for selling a stock
S = max(S, X+prices[i])``````

Java Implementation

``````public class Solution {
int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) return 0;
int s1=-prices[0], s2=Integer.MIN_VALUE,s3=Integer.MIN_VALUE,s4=Integer.MIN_VALUE;

for(int i=1;i<prices.length;++i) {
s1 = Math.max(s1, -prices[i]);
s2 = Math.max(s2, s1+prices[i]);
s3 = Math.max(s3, s2-prices[i]);
s4 = Math.max(s4, s3+prices[i]);
}
return Math.max(0,s4);
}
}``````

Solution

A Intuitive Implementation Using Divide And Conquer

``````import java.util.*;

public class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
// find maxProfit for {0, j}, find maxProfit for {j + 1, n - 1}
// find max for {max{0, j}, max{j + 1, n - 1}}

if (prices == null || prices.length == 0) {
return 0;
}

int maximumProfit = 0;
int n = prices.length;

ArrayList<Profit> preMaxProfit = new ArrayList<Profit>(n);
ArrayList<Profit> postMaxProfit = new ArrayList<Profit>(n);
for (int i = 0; i < n; i++) {
postMaxProfit.add(maxProfitHelper(prices, i + 1, n - 1));
}
for (int i = 0; i < n; i++) {
int profit = preMaxProfit.get(i).maxProfit + postMaxProfit.get(i).maxProfit;
maximumProfit = Math.max(profit, maximumProfit);
}
return maximumProfit;
}

private Profit maxProfitHelper(int[] prices, int startIndex, int endIndex) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = startIndex; i <= endIndex; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
}
if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return new Profit(maxProfit, minPrice);
}

public static void main(String[] args) {
int[] prices = new int[]{4,4,6,1,1,4,2,5};
Solution s = new Solution();
System.out.println(s.maxProfit(prices));
}
};

class Profit {
int maxProfit, minPrice;
Profit(int maxProfit, int minPrice) {
this.maxProfit = maxProfit;
this.minPrice = minPrice;
}
}``````

Another Implementation with Dynamic Programming

``````public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}

int[] left = new int[prices.length];
int[] right = new int[prices.length];

// DP from left to right;
left[0] = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
min = Math.min(prices[i], min);
left[i] = Math.max(left[i - 1], prices[i] - min);
}

//DP from right to left;
right[prices.length - 1] = 0;
int max = prices[prices.length - 1];
for (int i = prices.length - 2; i >= 0; i--) {
max = Math.max(prices[i], max);
right[i] = Math.max(right[i + 1], max - prices[i]);
}

int profit = 0;
for (int i = 0; i < prices.length; i++){
profit = Math.max(left[i] + right[i], profit);
}

return profit;
}
}``````

State Machine

``````class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
return maxProfit(prices, 2);
}
private int maxProfit(int[] array, int t) {
int[] stock = new int[t * 2];
Arrays.fill(stock, Integer.MIN_VALUE);
stock[0] = -array[0];
for(int i = 1; i < array.length; ++i) {
stock[0] = Math.max(stock[0], -array[i]);
for (int j = 1; j < 2 * t; j += 2) {
stock[j] = Math.max(stock[j], stock[j - 1] + array[i]);
if (j + 1 < 2 * t) {
stock[j + 1] = Math.max(stock[j + 1], stock[j] - array[i]);
}
}
}
return Math.max(0, stock[2 * t - 1]);
}
}``````

Last updated