Clean Java solution with O(n) time and O(1) space
First attempt - simple brute force solution (just coded up problem definition):\n\n    // O(n^2) time, O(1) space\n    public int maxProfit(int[] prices) {\n   
First attempt - simple brute force solution (just coded up problem definition):\n\n    // O(n^2) time, O(1) space\n    public int maxProfit(int[] prices) {\n        int profit = 0;\n        for (int i = 0; i < prices.length; i++) {\n            for (int j = i; j >= 0; j--) {\n                profit = Math.max(profit, prices[i]-prices[j]);\n            }\n        }\n        return profit;\n    }\n\nSecond attempt - tried to solve iterating over array two times:\n\nfirst pass - from left to right and saving current minimum in additional array \n\nsecond pass - from right to left finding maximum of current profit and previous maximum profit\n\n    // O(n) time, O(n) space\n    public int maxProfit(int[] prices) {\n        int[] minPrices = new int[prices.length];\n        int currentMinPrice = prices.length > 0 ? prices[0] : 0;\n        for (int i = 0; i < prices.length; i++) {\n            currentMinPrice = Math.min(currentMinPrice, prices[i]);\n            minPrices[i] = currentMinPrice;\n        }\n        \n        int currentMaxPrice = prices.length > 0 ? prices[prices.length - 1] : 0;\n        int profit = currentMaxPrice - currentMinPrice;\n        for (int i = prices.length - 1; i >= 0 ; i--) {\n            currentMaxPrice = Math.max(currentMaxPrice, prices[i]);\n            profit = Math.max(profit, currentMaxPrice - minPrices[i]);\n        }\n        return profit;\n    }\n\nThird attempt - finally figured out, that keeping current minimum in separate array is really not required:\n      \n    // O(n) time, O(1) space\n    public int maxProfit(int[] prices) {\n        int currentMinPrice = prices.length > 0 ? prices[0] : 0;\n        int profit = 0;\n        for (int i = 0; i < prices.length; i++) {\n            currentMinPrice = Math.min(currentMinPrice, prices[i]);\n            profit = Math.max(profit, prices[i] - currentMinPrice); \n        }\n        return profit;\n    }
['Array', 'Java']