Share my simple O(n) time solution


  • 3
    Z
    class Solution {
    public:
    	int maxProfit(vector<int> &prices) {
    		if (prices.empty())
    			return 0;
    		// dp stores the max profit before index i
    		vector<int>dp;
    		dp.resize(prices.size());
    		dp[0] = 0;
    		int mmin = prices[0];
    		for (int i = 1; i < prices.size() ; i++)
    		{
    			if (mmin>prices[i])
    			{
    				mmin = prices[i];
    				dp[i] = dp[i - 1];
    			}
    			else
    			{
    				dp[i] = max(dp[i - 1], prices[i] - mmin);
    			}
    		}
    		// dp1 stores the max profit after index i
    		vector<int>dp1;
    		dp1.resize(prices.size());
    		dp1[prices.size()-1] = 0;
    		int mmax = prices.back();
    		for (int i = prices.size()-2; i >=0 ; i--)
    		{
    			if (mmax<prices[i])
    			{
    				mmax = prices[i];
    				dp1[i] = dp1[i + 1];
    			}
    			else
    			{
    				dp1[i] = max(dp1[i + 1], mmax-prices[i]);
    			}
    		}
            // res = max{dp[i]+dp1[i]}
    		int res = 0;
    		for (int i = 0; i < prices.size() ; i++)
    		{
    			if (res < dp[i] + dp1[i])
    				res = dp[i] + dp1[i];
    		}
    		return res;
    	}
    };

  • 8
    R

    I think mine is really simple.

    class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            
            if (prices.size()<2) return 0;
            int len=prices.size(),result=0;
            int low=prices[0],high=prices[len-1];
            
            vector<int> profits_history(len,0);
            
            for (int i=0;i<len;i++){
                low=min(low,prices[i]);
                result=max(result,prices[i]-low);
                profits_history[i]=result; 
            }
            
            for (int i=len-1;i>=0;i--){
                high=max(high,prices[i]);
                result=max(result,high-prices[i]+profits_history[i]);
            }
            return result;
        }
    };

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    H

    You share the same idea with me. However, I am thinking if there is a solution where only one traversal of the list is needed. You know, we can expect questions like this in a job interview.


  • 0
    R

    I think in your first for loop, you don't need to keep update the result.
    after the for loop, result must equals profits_history[prices.length - 1]


Log in to reply
 

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