O(n) detailed explanation. CASE DISSECTED!!
5, 2, 6, 1, 4\nLet us solve the problem for the above data\nDays are numbered, from 0 to 4 (i = i to 4)\n\nPrimary idea: Buying at the lowest price and selling 
# 5, 2, 6, 1, 4\n**Let us solve the problem for the above data**\nDays are numbered, from 0 to 4 (i = i to 4)\n\nPrimary idea: Buying at the lowest price and selling it at the maximum will bring us profit! We always look for maximum profit if we cannot sell it at lowest or buy it at its highest.\n\n**Day 0: [5]** \n*We have one option. Let us suppose we buy the stock at day 0. **minbytsofar=5.**\nLet us suppose we sold it at Day 0 itself. Thus, we sold it at 5.\nRemember profit= sell cost- buy cost. What will be the profit in this case? **profit=5-5=0***\n\n**Day 1: [5 , 2]**\n*On day 1 we see that if we bought it now, instead of buying it when the cost was 5, we will be at an advantage. Because, our primary idea was to buy at the lowest. Thus, **minbuysofar**= **minimum(5,2)= 2**\nSelling it at day 1 will give us a **profit=2-2=0***\n\n**Day 2: [5, 2, 6]**\n*If we bought it on day 2, we wont be making an intellingent choice, because we always buy stock at its minimum. We let the minbuysofar remain as it was. Mathematically, **minbuysofar=minimum(6,2)=2***\n*Selling it now would give us a profit of (selling at day 2- buying at day 1)= **profit=6-2=4***\n*setting a global maxima for profit, maxprofit=4*\n\n**Day 3: [5, 2, 6, 1]**\n*The price is 1 now. Will we buy now? Hell yeah!! Its lower than 2 **minbuysofar=minimum(2,1)***\n***profit=selling it on day 3- buying it on day 3=1-1=0***\n*Global maxima for profit? Maximum(0,4)=4. 4 was still our maximum profit made*\n\n**Day 4: [5, 2, 6, 1, 4]**\n***minbuysofar= minimum(1,4)*** *We won\'t buy anymore*\n*Maximum profit made is still 4. Because Max(4,3)=4*\n\n**Answer = 4. OUR BEST PROFIT!!**\n\n\n```\nclass Solution {\n    public int maxProfit(int[] prices) {\n        if (prices.length == 1)\n            return 0;\n        \n        //              DYNAMIC PROGRAMMING APPROACH  \n        \n        //we are going to run a loop and find selling on which day is going to give us profit, corresponding to each buying day\n        //to optimize this we further find the best buying day before calculating the profit\n        \n        int minbuysofar = prices [0];\n        int maxprofit = 0;\n        int profit = 0;\n        \n        for (int i=0; i<prices.length; i++)\n        {\n            minbuysofar = Math.min(minbuysofar, prices[i]);\n            //we buy at the price of minbuysofar\n            \n            \n            profit = prices[i]- minbuysofar; \n            /* this translates to:\n        minbuysofar = selling on i\'th day- buying when price is minbuysofar*/\n            \n            \n            //Now we need to see where the profit was maximum\n            maxprofit = Math.max(maxprofit, profit);\n        }\n        \n        return maxprofit;\n}\n}\n```\n\n***upvote if you find this helpful :p***
['Array', 'Dynamic Programming', 'C', 'Java']