Cpp solution beats 72 percent


  • 0
    S
    class Solution {
    public:
        int findMax(int a, int b){
            return a>b? a:b;
        }
        int findMin(int a, int b){
            return a<b? a:b;
        }
        int maxProfit(vector<int>& prices) {
            int n = prices.size();
            if(n==0) return 0;
            int left[n], min=0, max=0, profit=0;
            left[0] =0, min= prices[0];
            //Compute max profits till day i
            for(int i=1; i<n; i++){
                left[i] = findMax(left[i-1], prices[i]-min);
                min = findMin(min, prices[i]);
            }
            int right[n];
            right[n-1] = 0, max= prices[n-1];
            //Compute max profits from day i+1 to last
            for(int i=n-2; i>=0; i--){
                right[i] = findMax(right[i+1], max- prices[i]);
                max = findMax(max, prices[i]);
            }
            for(int i=0; i<n-1; i++)
                profit = findMax(profit, left[i]+right[i+1]);
            profit = findMax(profit, left[n-1]);
            return profit;
        }
    };

Log in to reply
 

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