This page explains Java solution to problem Best Time to Buy and Sell Stock III using Dynamic Programming algorithm.
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.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:Example 2:Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation:
Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Input: prices = [1,2,3,4,5]
Output: 4
Explanation:
Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
package com.vc.hard;
import java.util.*;
class BestTimeToBuyAndSellStockIii {
public int maxProfit(int[] prices) {
/**
Input:
[3 3 5 0 0 3 1 4]
1 2 3 4 5 6 7 8
k = 2
Number of transactions allowed is 2, which means 2 Buys and 2 Sells are allowed
Explanation:
dp_i_0[k] -> Profit on ith day after k transaction and zero stock in hand at end of day
dp_i_1[k] -> Profit on ith day after k transactions and one stock in hand at end of day
Formula:
dp_i_1[j] = Math.max(dp_i_1[j], dp_i_0[j - 1] - prices[i])
-> On ith Day we can either do nothing which gives us dp_i_1[j] profit
-> Or Perform buy which gives us dp_i_0[j - 1] - prices[i]
-> dp_i_0[j - 1] because we buy stock with profit made until previous transaction
and previous transaction has to be sell because we can't buy again before we sell
-> - prices[i] because we buy with current days price
dp_i_0[j] = Math.max(dp_i_0[j], dp_i_1[j] + prices[i])
-> On ith Day we can either do nothing which gives us dp_i_0[j] profit
-> Or Perform sell which gives us dp_i_1[j] + prices[i]
-> dp_i_1[j] because we sell stock which was bought at 1st best price
-> + prices[i] because we get profit after selling stock
0th Day
dp_i_1 [-I, -I, -I]
dp_i_0 [0, 0, 0]
1st Day = 3
dp_i_1 [-I, -3, -3]
dp_i_0 [ 0, 0, 0]
2nd Day = 3
dp_i_1 [-I, -3, -3]
dp_i_0 [ 0, 0, 0]
3rd Day = 5
dp_i_1 [-I, -3, -3]
dp_i_0 [ 0, 2, 2]
4th Day = 0
dp_i_1 [-I, 0, 2]
dp_i_0 [ 0, 2, 2]
5th Day = 0
dp_i_1 [-I, 0, 2]
dp_i_0 [ 0, 2, 2]
6th Day = 3
dp_i_1 [-I, 0, 2]
dp_i_0 [ 0, 3, 5]
7th Day = 1
dp_i_1 [-I, 0, 2]
dp_i_0 [ 0, 3, 5]
8th Day = 4
dp_i_1 [-I, 0, 2]
dp_i_0 [ 0, 4, 6]
*/
int n = prices.length;
if(n <= 1) return 0;
int[] dp_i_0 = new int[3];
int[] dp_i_1 = new int[3];
Arrays.fill(dp_i_1, Integer.MIN_VALUE);
for(int i = 0; i < prices.length; i++) {
for(int j = 1; j <= 2; j++) {
//Rest or Sell on ith Day
dp_i_0[j] = Math.max(dp_i_0[j], dp_i_1[j] + prices[i]);
//Rest or Buy on ith Day, When we Buy number of transaction reduces by 1
dp_i_1[j] = Math.max(dp_i_1[j], dp_i_0[j - 1] - prices[i]);
}
}
return dp_i_0[2];
}
}
O(N) Where
N is total number of days
O(1)