Very very easy understanding algorithm, O(n)


  • 1
    J
    int maxProfitNew(vector<int>& prices) {
    	if(prices.size()==0) return 0;
    	vector<int> leftMax(prices.size(), 0);
    	vector<int> rightMax(prices.size(), 0);
    	int minPrice = prices[0];
    	for(int i=1,size=prices.size();i<size;++i) {
    		minPrice = min(minPrice, prices[i]);
    		leftMax[i] = max(prices[i]-minPrice, leftMax[i-1]);
    	}
    	int maxPrice = prices.back();
    	for(int i=prices.size()-2;i>=0;--i) {
    		maxPrice = max(maxPrice, prices[i]);
    		rightMax[i] = max(maxPrice-prices[i], rightMax[i+1]);
    	}
    	int temp, maxProfit = 0;
    	for(int i=0,size=prices.size();i<size;++i) {
    		temp = leftMax[i]+rightMax[i];
    		if(temp>maxProfit) maxProfit = temp;
    	}
    	return maxProfit;
    }
    

Log in to reply
 

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