# [Java/C++] Clean Code (DP/Greedy)

• Java DP

``````class Solution {
public int maxProfit(int[] p, int fee) {
int n = p.length;
if (n < 2) return 0;
int[] hold = new int[n], sold = new int[n];
hold[0] = -p[0];
for (int i = 1; i < n; ++i) {
hold[i] = Math.max(hold[i - 1], sold[i - 1] - p[i]);
sold[i] = Math.max(sold[i - 1], hold[i - 1] + p[i] - fee);
}

return sold[n - 1];
}
}
``````

C++ DP

``````class Solution {
public:
int maxProfit(vector<int>& p, int fee) {
int n = p.size();
if (n < 2) return 0;
vector<int> hold(n, 0), sold(n, 0);
hold[0] = -p[0];
for (int i = 1; i < n; i++) {
hold[i] = max(hold[i - 1], sold[i - 1] - p[i]);
sold[i] = max(sold[i - 1], hold[i - 1] - fee + p[i]);
}

return sold[n - 1];
}
};
``````

Java Greedy

1. buy in - when current price higher than previous lowest point by more than amount of transaction fee, and set current price as highest point;
2. sale out - when current price lower than prevous highest point by more than amount of transaction fee, and reset lowest, highest
3. update highest - only if highest is set;
4. update lowest - every day
``````class Solution {
public int maxProfit(int[] p, int fee) {
int profit = 0;
Integer lo = null, hi = null, n = p.length;
for (int i = 0; i < n; i++) {
if (lo != null && hi == null && p[i] - lo > fee) hi = p[i]; // buy in
if (hi != null && p[i] > hi) hi = p[i]; // update highest
if (hi != null && (hi - p[i] > fee || i == n - 1)) { // sale out
profit += hi - lo - fee;
hi = null;
lo = null;
}

lo = lo != null ? Math.min(lo, p[i]) : p[i]; // update lowest
}
return profit;
}
}
``````

C++ Greedy

``````class Solution {
public:
int maxProfit(vector<int>& p, int fee) {
int profit = 0;
int* lo = nullptr, *hi = nullptr, n = p.size();
for (int i = 0; i < n; i++) {
if (lo && !hi && p[i] - *lo > fee) hi = &p[i]; // buy in
if (hi && p[i] > *hi) hi = &p[i]; // update highest
if (hi && (*hi - p[i] > fee || i == n - 1)) { // sale out
profit += *hi - *lo - fee;
hi = nullptr;
lo = nullptr;
}

if (!lo || p[i] < *lo) lo = &p[i]; // update lowest
}
return profit;
}
``````

• @alexander Nice solution. For your dp solution, could you please explain why you did not initialize unhold[0] = -fee ? For example, if I buy a share and sell a share on first day, should net profit be negative in this case?

• Good question, I think in reality you could. But in this problem, buy & sale on the same day never make its way to be an option in terms of profitability.
BTW, I changed the variable `unhold` to `sold`.

• @alexander Thanks for your explanation. But I'm still little confused... Let's say sold[i] represents the max profit on ith day with last transaction sold. Then sold[0] will be the max profit you sold on your first day which will be -fee since you have to buy first.

I think in previous buy & sell stock series, we imply the scenario of buying and selling on the same since it will never change the profit. But will transaction fee, I would say it is still possible if we represent the recurrence in the same way.