Java all approach - Recursive, DP,  Kadane's Algorithm
Algorithm\n This is one of the popular interview question and I would like to expalin in a way that I understood\n\nRecursive Approach\n The base case is that i
**Algorithm**\n* This is one of the popular interview question and I would like to expalin in a way that I understood\n\n**Recursive Approach**\n* The base case is that if the index passed to the recursive function has reached the `prices` array length, if so `return 0`\n* compute the minimum of the current item, `prices[index]` so that when we backtrack after the recursive call we can compute `maxProfit` by comparing with the current element difference with the `prices[index]`\n* recursively call the function by incrementing the `index`, the value that will be returned from recursive call is the `maxProfit`\n* after coming from the recursive call, we cmpute the maxProfit with the current element `prices[index] - min` element found before recursing.\n\n```\nclass Solution {\n     protected int dfs(int[] prices, int index, int min){\n         if (index == prices.length)\n             return 0;\n        \n         int minimumEndingHere = Math.min(min, prices[index]);\n         int maxProfit = dfs(prices, index + 1, minimumEndingHere);\n         maxProfit = Math.max(maxProfit, prices[index] - min);\n         return maxProfit;\n     }\n     public int maxProfit(int[] prices) {\n         return dfs(prices, 0, Integer.MAX_VALUE);\n   }\n}\n```\n\n**O(N) - Bottom Up Approach**\n* start with having the dp array of the length of the `prices` array\n* At each index store the max of the difference with the `prices[i]` with `min` that was computed earlier\n* update the `min` everytime comparing with the current price\n\n```\nclass Solution {\npublic int maxProfit(int[] prices) {\n        if (prices.length == 0)\n            return 0;\n        int[] dp = new int[prices.length];\n        int min = prices[0];\n    \n        for (int i=1;i<prices.length;i++){\n            dp[i] = Math.max(dp[i-1], prices[i] - min);\n            min = Math.min(min, prices[i]);\n        }\n        \n        return dp[prices.length-1];\n    }\n}\n```\n\n**O(N) - Kadane\'s Algorithm**\n* assign `maxEndingHere` and `minEndingHere` with the first element in the prices array\n* Loop through the length of the `prices` array\n* If at any time you see `prices[i] < max`, then assign the `maxEndingHere` to the `prices[i]`, this is because we have to have the max computed after we buy the share for minimum prices. So we need to compute everytime\n* Get the `maxEndingHere` and `minEndingHere` as the max and min compared with the `prices[i]`\n* Compute `maxProfit` as the max between computed `maxEndingHere` and the difference of `maxEndingHere` and `minEndingHere`\n* return the `maxProfit`\n```\nclass Solution {\npublic int maxProfit(int[] prices) {\n\nif (prices == null || prices.length == 0)\n     return 0;\n        int maxProfit = 0;\n         int maxEndingHere = prices[0];\n         int minEndingHere = prices[0];\n        \n         for (int i=1;i<prices.length;i++){\n             if (prices[i] < maxEndingHere){\n                 maxEndingHere = prices[i];\n             }\n            maxEndingHere = Math.max(maxEndingHere, prices[i]);\n            minEndingHere = Math.min(minEndingHere, prices[i]);\n            maxProfit = Math.max(maxProfit, Math.abs(maxEndingHere-minEndingHere));\n         }\n         return maxProfit;\n\t}\n}\n```
['Dynamic Programming', 'Recursion', 'Java']