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.
1class Solution {
2 public int maxProfit(int[] prices, int fee) {
3 int cash = 0, hold The Java solution follows the same logic as the C/C++ implementations. Variables cash and hold are updated each day to track the best outcomes possible for those states. Transitional decisions are handled with Math.max, ensuring maximum profit.
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.