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


  • 3

    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;
        }
    

  • 0
    T

    @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?


  • 0

    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.


  • 0
    T

    @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.

    Looking forward to your answer :D


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.