Exhaustive Search / DP with Explanation (Java / Python)
Exhaustive Search\nThe problem is to get the maximum (prices[j] - prices[i]) for 0 <= i < j <= price.length,\nAny price maycanbe the candidate prices[j].\nTo ge
> **Exhaustive Search**\nThe problem is to get the maximum (prices[j] - prices[i]) for 0 <= i < j <= price.length,\nAny price maycanbe the candidate prices[j].\nTo get the maximum (prices[j] - prices[i]), prices[i] should be the minimum value to the left of prices[j].\n```\n    public int maxProfit(int[] prices) {\n        int minPriceSoFar = Integer.MAX_VALUE, maxProfitSoFar = 0;\n        \n        for (int i = 0; i < prices.length; i++) {\n            if (minPriceSoFar > prices[i]) {\n                minPriceSoFar = prices[i];\n            } else {\n                maxProfitSoFar = Math.max(maxProfitSoFar, prices[i] - minPriceSoFar);\n            }\n        }\n        \n        return maxProfitSoFar;\n    }\n```\n\n> **Dynamic Programming**\nThe maximum profit is actually the maximum consecutively increasing difference.\nThe maximum consecutively increasing difference can end at any element in nums.\nThe maximum consecutively increasing difference ending at position i + 1 is\neither includes maximum consecutively increasing difference ending at position i or it doesn\'t.\nThat can be solved in the way similar to [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/discuss/132821/DP-Thinking-Process-with-Java-Code).\n****\n```\n    public int maxProfit(int[] prices) {\n        int n = prices.length, maxProfitSoFar = 0;\n        // maxIncDiffSum[i] max sum of increasing difference ending at prices[i].\n        int[] maxIncDiffSum = new int[n];\n        \n        for (int i = 1; i < n; i++) {\n            maxIncDiffSum[i] = Math.max(0, maxIncDiffSum[i - 1] + prices[i] - prices[i - 1]);\n            maxProfitSoFar = Math.max(maxProfitSoFar, maxIncDiffSum[i]);\n        }\n        \n        return maxProfitSoFar;\n    }\n```\n```\n    def maxProfit(self, prices):\n        if len(prices) <= 1:\n            return 0\n        \n        lenPrices = len(prices)\n        state = [0] * lenPrices\n        for i in range(1, lenPrices):\n            state[i] = max(state[i - 1] + prices[i] - prices[i - 1], 0)   \n            \n        return max(state)\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]