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
一种算法比较容易想到：
找寻一个点j，将原来的prices[0..n-1]分割为prices[0..j]和prices[j..n-1]，分别求两段的最大profit。
内层循环与Best Time to Buy and Sell Stock相同，为O(n), 外层循环为O(n)，记录不同的j两段maxProfit的值需要O(n)空间，因此总体时间复杂度为O(n^2)，空间复杂度为O(n)。
改进（参考pickless的讲解）:
对于点j+1，求prices[0..j+1]的最大profit时，很多工作是重复的，在求prices[0..j]的maxProfit中已经计算过了。
类似于Best Time to Buy and Sell Stock，可以在O(1)的时间从prices[0..j]推出prices[0..j+1]的最大profit。
但是如何从prices[j..n-1]推出prices[j+1..n-1]？反过来思考，我们可以用O(1)的时间由prices[j+1..n-1]推出prices[j..n-1]。
最终算法：
数组l[i]记录了prices[0..i]的最大profit，
数组r[i]记录了prices[i..n]的最大profit。
已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。
最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。
这样时间复杂度O(n), 空间复杂度O(n)
// 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])
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++) {
preMaxProfit.add(maxProfitHelper(prices, 0, 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]);
}
}