121. Best Time to Buy and Sell Stock Leetcode Java

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution:

All relevant problems:

188. Best Time to Buy and Sell Stock IV 

123.Best Time to Buy and Sell Stock III

122. Best Time to Buy and Sell Stock II

121. Best Time to Buy and Sell Stock I

Use the same technique as maximum subarray. Localmax and globalmax.

Definitely, the maximum profit must be buy at one day, and sell on a later day.So if we know what is the best profit for selling the stock in each day, then we can know the global maximum profit by comparing all those localMax. 

The recursion equation is : localMax[i]=Math.max(0,localMax[i-1]+prices[i]-prices[i-1]). 

Clearly, LocalMax[i-1]=prices[i-1]-prices[j],where prices[j] is the lowest price before prices[i].(j<=i-1). If prices[i]>prices[j], then localMax[i]=prices[i]-prices[j]=localMax[i-1]+prices[i]-prices[i-1]. If prices[i]<prices[j], then the maximum profit should be buy and sell on the same day ith day, so, localmax[i]=0. Therefore: localMax[i]=Math.max(0,localMax[i-1]+prices[i]-prices[i-1])

During the iteration for calculating localMax[i], update globalMax accordingly. 

Time compleixty: O(n), constant space.

 public int maxProfit(int[] prices) {  
     if(prices==null || prices.length<=1) return 0;  
     int localMax=0;  
     int globalMax=0;  
     for(int i=1;i<prices.length;i++){  
       localMax=Math.max(localMax+prices[i]-prices[i-1],0);  
       globalMax=Math.max(localMax,globalMax);  
     }  
     return globalMax;  
   }