Kadane's Algorithm - Since no one has mentioned about this so far :) (In case if interviewer twists the input)
The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing
The logic to solve this problem is same as "max subarray problem" using `Kadane's Algorithm`. Since no body has mentioned this so far, I thought it's a good thing for everybody to know. \n\nAll the straight forward solution should work, but if the interviewer twists the question slightly by giving the ***difference array of prices***, Ex: for `{1, 7, 4, 11}`, if he gives `{0, 6, -3, 7}`, you might end up being confused. \n\nHere, the logic is to calculate the difference (`maxCur += prices[i] - prices[i-1]`) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.\n\n\n        public int maxProfit(int[] prices) {\n            int maxCur = 0, maxSoFar = 0;\n            for(int i = 1; i < prices.length; i++) {\n                maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);\n                maxSoFar = Math.max(maxCur, maxSoFar);\n            }\n            return maxSoFar;\n        }\n\n*`maxCur = current maximum value`\n\n*`maxSoFar = maximum value found so far`
['Dynamic Programming']