Sponsored
Sponsored
In this approach, we use Dynamic Programming to manage two states: whether you're holding a stock or not on each day. The goal is to maximize the profit by deciding to buy, sell, or hold at each step while accounting for the transaction fee.
States: We define two states: hold[i] which represents the maximum profit you can have on day i when holding a stock, and cash[i] which represents the maximum profit on day i when not holding a stock.
State Transitions: On each day, you can either buy a stock (thus moving from cash[i-1] to hold[i]) or sell a stock (thus moving from hold[i-1] to cash[i]). Decisions should include transaction fee accordingly.
Time Complexity: O(N), where N is the number of days, since we go through the prices once.
Space Complexity: O(1), as we use a fixed amount of extra space regardless of input size.
1#include <stdio.h>
2
3int maxProfit(int* prices, int pricesSize, int fee) {
4 if (
The C solution uses two variables, cash and hold, to keep track of the two states we have defined. Initially, cash is set to 0 (since you start with no money from stock), and hold is set to -prices[0] (representing buying a stock on the first day).
For each day, update cash with the maximum of not selling today or selling the stock today with added profit minus fee. Similarly, hold is updated with the maximum of not buying today or buying today by using available cash.
The greedy approach is an alternative solution that strives to maximize the profit by considering local optimal decisions. Unlike the dynamic approach that tracks two states, this method attempts to buy on dips and sell at peaks whenever possible while covering the transaction fee.
Keep track of the lowest price at which a stock might have been bought, and compare future prices to decide if selling should occur, adjusting the buy price to be less the transaction fee.
Time Complexity: O(N), since it processes each price once.
Space Complexity: O(1), using a constant set of additional variables.
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int maxProfit = 0;
int minPrice = prices[0];
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] > minPrice + fee) {
maxProfit += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return maxProfit;
}
};
int main() {
vector<int> prices = {1, 3, 2, 8, 4, 9};
int fee = 2;
Solution sol;
int result = sol.maxProfit(prices, fee);
return 0;
}In C++, the implementation mirrors the C code in logic and optimizes the decision to buy/sell stocks based on the greed for maximum profit post-fee consideration. It dynamically recalculates each minimum purchase point.