A O(1*n)  solution
1.for prices[0] .... prices[n], prices[n+1].....\nif (prices[n] < prices[0]) then, the max profit is in prices[0]...prices[n], or begin from prices[n+1],\nother
1.for prices[0] .... prices[n], prices[n+1].....\nif (prices[n] < prices[0]) then, the max profit is in prices[0]...prices[n], or begin from prices[n+1],\notherwise, suppose prices[n+1] > prices[0], and max profit is happened between prices[n+1] , and \nprices[n+k](k>1), then if we buy at day 0, and sell at day n+k, we get a bigger profit.\n\nBase on logic above, we can have a O(1*n) solution:\n\n    public class Solution {\n        public int maxProfit(int[] prices) {\n            \n            if (prices.length == 0)\n            {\n                return 0;\n            }\n            \n            int max = 0, min = prices[0];\n            int profit = 0;\n            \n            for (int i = 1; i < prices.length; i++)\n            {\n                if (prices[i] < min)\n                {\n                    \n                    min = prices[i];\n                }\n                else\n                {\n                    if (prices[i] - min > profit)\n                    {\n                        profit = prices[i] - min;\n                    }\n                    \n                }\n            }\n         \n       \n         \n         return profit;\n         \n        }\n    }
[]