Sharing my simple java solution, easy to understand


  • 0
    D

    My solution is like this: if a subarray start with a minimum number, than this number will be the date you buy the stock. So during the scan of the array, always keep the minimum number of the subarray in ascending order, when a small number comes, calculate the difference between the last number and our minimum number, and compare this number with the minimum number we have, then update if this number was smaller. So we can find the maximum profit in O(N) time since we only have to go through the whole array once.

    public int maxProfit(int[] prices) {
            if (prices.length < 1) return 0;
            int min = prices[0];
            int temp = 0;
            int maxpro = 0;
            for (int i = 1; i < prices.length; i++)
            {
                if (prices[i] < min) min = prices[i];
                else 
                {
                    temp = prices[i] - min;
                }
                if (temp > maxpro) maxpro = temp;
            }
            return maxpro;
        }
    

Log in to reply
 

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