Java 2ms Solution Dynamic


  • 0
    M

    Java solution uses a variable to store a day for cheapest purchase price and a variable to store the greatest profit from buying and selling. Note that the first variable could be replaced simply with the cheapest purchase price itself.

    Runs in linear time because it performs one pass through of the input. Using the variables to store/update max profit and cheapest purchase price allows up to reduce runtime from quadratic to linear.

    public class Solution {
        public int maxProfit(int[] prices) {
            int cheapestDay = 0;
            int maxProfit = 0;
            if (prices.length <= 1) {
                return 0;
            } else if (prices.length == 2) {
                return Math.max(0, prices[1] - prices[0]);
            } else {
                for (int i = 0; i < prices.length; i++) {
                    cheapestDay = (prices[cheapestDay] > prices[i]) ? i : cheapestDay;
                    maxProfit = (prices[i] - prices[cheapestDay] > maxProfit) ? 
                        prices[i] - prices[cheapestDay] : maxProfit;
                }
                return maxProfit;
            }
        }
    }
    

Log in to reply
 

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