Best Time to Buy and Sell Stock III Editorial

Practice Problem Link: Best Time to Buy and Sell Stock III

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given an array price where prices[i] denotes the price of a stock on the ith day. You want to maximize the profit by buying a stock and then selling it at a higher price.

Suppose you can do at most two transactions (two buys and two sells), what is the maximum profit that you can make?

Note:

• Return 0 if you cannot make a profit.
• You cannot buy/hold more than 1 stock at a time.
• You need to sell a stock before buying again.
• You can sell a stock and buy it again on the same day.

Naive Approach

A simple solution is to traverse the given array and for every index i calculate the max profit from 0 to i and i+1 to n subarrays doing at most one transaction on each subarray. The maximum value obtained among all the indexes will be the final answer.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int getMaxProfit(vector<int> &prices, int start, int end) {
    int profit = 0, minPrice = INT_MAX;
	for(int i = start; i <= end; i++) {
		minPrice = min(minPrice, prices[i]);
		profit = max(profit, prices[i] - minPrice);
	}
	return profit;
}
int maxProfit(vector<int> &prices) {
    int profit = 0;
	for (int i = 0; i < prices.size(); i++) {
		profit = max(profit, getMaxProfit(prices, 0, i) + getMaxProfit(prices, i + 1, prices.size() - 1));
	}
	return profit;
}

Java

class Solution {
	int getMaxProfit(int[] prices, int start, int end) {
		int profit = 0, minPrice = Integer.MAX_VALUE;
		for(int i = start; i <= end; i++) {
			minPrice = Math.min(minPrice, prices[i]);
			profit = Math.max(profit, prices[i] - minPrice);
		}
		return profit;
	}
	int maxProfit(int[] prices) {
	    int profit = 0;
		for (int i = 0; i < prices.length; i++) {
			profit = Math.max(profit, getMaxProfit(prices, 0, i) + getMaxProfit(prices, i + 1, prices.length - 1));
		}
		return profit;
	}
}

Optimal Approach

The idea is to create two arrays say leftMaxProfit and rightMaxProfit to store the profit of the subarrays.

• Traverse the given array from start to end and for each i update leftMaxProfit[i] to maximum profit that can be obtained from 0 to i by doing at most one transaction.
• Traverse the given array from end to start and for each index i update rightMaxProfit[i] to maximum profit that can be obtained from i to n by doing at most one transaction.
• Now traverse both the arrays and update the answer as max(answer, leftMaxProfit[i] + rightMaxProfit[i]) for every i.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int maxProfit(vector<int> &prices) {
	int n = prices.size();
	int leftMaxProfit[n] = {0}, rightMaxProfit[n] = {0};
	int minPrice = prices[0];
	for (int i = 1; i < n; i++) {
		minPrice = min(minPrice, prices[i]);
		leftMaxProfit[i] = max(leftMaxProfit[i - 1], prices[i] - minPrice);
	}
	int maxPrice = prices[n - 1];
	for (int i = n - 2; i >= 0 ; i--) {
		maxPrice = max(maxPrice, prices[i]);
		rightMaxProfit[i] = max(rightMaxProfit[i + 1], maxPrice - prices[i]);
	}
	int profit = 0;
	for (int i = 0; i < n; i++) {
		profit = max(profit, rightMaxProfit[i] + leftMaxProfit[i]);
	}
	return profit;
}

Java

class Solution {
	int maxProfit(int[] prices) {
	    int n = prices.length;
		int[] leftMaxProfit = new int[n], rightMaxProfit = new int[n];
		int minPrice = prices[0];
		for (int i = 1; i < n; i++) {
			minPrice = Math.min(minPrice, prices[i]);
			leftMaxProfit[i] = Math.max(leftMaxProfit[i - 1], prices[i] - minPrice);
		}
		int maxPrice = prices[n - 1];
		for (int i = n - 2; i >= 0 ; i--) {
			maxPrice = Math.max(maxPrice, prices[i]);
			rightMaxProfit[i] = Math.max(rightMaxProfit[i + 1], maxPrice - prices[i]);
		}
		int profit = 0;
		for (int i = 0; i < n; i++) {
			profit = Math.max(profit, rightMaxProfit[i] + leftMaxProfit[i]);
		}
		return profit;
	}
}