Best Time to Buy and Sell Stock IV Editorial

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

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 k transactions (k buys and k 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

The idea to solve this problem is based on dynamic programming.

Let's say profit[i][j] represents maximum profit obtained by doing i transitions till jth day.

Then the DP state will be profit[i][j] = max(max(profit[i - 1][day] + prices[j] - prices[day]), profit[i][j - 1])  for all day between 0 to j-1. i.e. maximum profit that can be obtained by doing at most i transitions on jth day will be maximum of doing a transition on that day or not doing a transition on that day.

• To get the maximum profit by doing a transaction on jth day we need to pick a day between 0 to j - 1 on which the stock must be bought and the profit will be maximum. This can be done by traversing the given array. Let's say the day on which stock is bought is represented by day. Then the maximum profit that can be obtained in this case will be profit[i - 1][day] + prices[j] - prices[day].
• Not doing a transaction on jth day can be simply calculated as profit till the previous day(profit[i][j - 1]).

Analysis

• Time Complexity: O(n2 * k)
• Auxiliary Space Complexity: O(n * k)

Implementation

C++

int maxProfit(vector<int> &prices, int k) {
	int n = prices.size();
    int profit[k + 1][n + 1];
	for (int i = 0; i <= k; i++) {
	    profit[i][0] = 0;
	}
	for (int i = 0; i <= n; i++) {
		profit[0][i] = 0;
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j < n; j++) {
			int currMax = INT_MIN;
			for (int day = 0; day < j; day++) {
				currMax = max(currMax, prices[j] - prices[day] + profit[i - 1][day]);
			}
			profit[i][j] = max(profit[i][j - 1], currMax);
		}
	}
	return profit[k][n - 1];
}

Java

class Solution {
	int maxProfit(int[] prices, int k) {
	    int n = prices.length;
		int profit[][] = new int[k + 1][n + 1];
		for (int i = 0; i <= k; i++) {
			profit[i][0] = 0;
		}
		for (int i = 0; i <= n; i++) {
			profit[0][i] = 0;
		}
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j < n; j++) {
				int currMax = Integer.MIN_VALUE;
				for (int day = 0; day < j; day++) {
					currMax = Math.max(currMax, prices[j] - prices[day] + profit[i - 1][day]);
				}
				profit[i][j] = Math.max(profit[i][j - 1], currMax);
			}
		}
		return profit[k][n - 1];
	}
}

Optimal Approach

The optimal is quite similar to the naive approach.

In the above mentioned DP state, max(profit[i - 1][day] + prices[j] - prices[day]) can also be written as prices[j] + max(profit[i - 1][day] - prices[day]). Since j will be constant for a particular day max(profit[i - 1][day] - prices[day]) can be computed in the same traversal in another variable say prevMaxProfit as max(prevMaxProfit, profit[i - 1][j] - prices[j] to reduce the time complexity.

Analysis

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

Implementation

C++

int maxProfit(vector<int> &prices, int k) {
	int n = prices.size();
    int profit[k + 1][n + 1];
	for (int i = 0; i <= k; i++) {
	    profit[i][0] = 0;
	}
	for (int i = 0; i <= n; i++) {
		profit[0][i] = 0;
	}
	for (int i = 1; i <= k; i++) {
		int prevMaxProfit = INT_MIN;
		for (int j = 1; j < n; j++) {
			prevMaxProfit = max(prevMaxProfit, profit[i - 1][j - 1] - prices[j - 1]);
			profit[i][j] = max(profit[i][j - 1], prices[j] + prevMaxProfit);
		}
	}
	return profit[k][n - 1];
}

Java

class Solution {
	int maxProfit(int[] prices, int k) {
	    int n = prices.length;
		int profit[][] = new int[k + 1][n + 1];
		for (int i = 0; i <= k; i++) {
			profit[i][0] = 0;
		}
		for (int i = 0; i <= n; i++) {
			profit[0][i] = 0;
		}
		for (int i = 1; i <= k; i++) {
			int prevMaxProfit = Integer.MIN_VALUE;
			for (int j = 1; j < n; j++) {
				prevMaxProfit = Math.max(prevMaxProfit, profit[i - 1][j - 1] - prices[j - 1]);
				profit[i][j] = Math.max(profit[i][j - 1], prices[j] + prevMaxProfit);
			}
		}
		return profit[k][n - 1];
	}
}