Java || Dynamic Programming || O(n)
Intuition\nThe problem involves finding the maximum profit that can be obtained by buying and selling a stock. The intuition is to use dynamic programming to ke
# Intuition\nThe problem involves finding the maximum profit that can be obtained by buying and selling a stock. The intuition is to use **dynamic** **programming** to keep track of the minimum buying price and the maximum profit that can be obtained at each step.\n\n# Approach\n- Check if the length of the `prices` array is less than or equal to 1. If so, return 0 because there are not enough days to make a profit.\n- Initialize an integer array `dp` of the same length as `prices` to store the maximum profit that can be obtained at each day. Set `dp[0]` to 0 because no profit can be made on the first day.\n- Initialize an integer variable `minPrice` to store the minimum buying price. Set `minPrice` to the price on the first day, `prices[0]`.\n- Use a loop to iterate through the `prices` array starting from the second day (index 1).\n- For each day `i`, calculate the maximum profit that can be obtained either by not selling on this day (i.e., `dp[i-1]`) or by selling on this day (i.e., `prices[i] - minPrice`). Take the maximum of these two values and update `dp[i]` accordingly.\n- Update `minPrice` by taking the minimum of its current value and the price on the current day `prices[i]`. This step ensures that `minPrice` always represents the minimum buying price seen so far.\n- After the loop, the maximum profit is stored in `dp[n-1]`, where `n` is the length of the `prices` array.\n- Return `dp[n-1]` as the maximum profit that can be obtained.\n\n# Complexity\n- Time complexity: O(n)\n  The algorithm iterates through the `prices` array once, performing constant-time operations at each step, resulting in a linear time complexity of O(n), where n is the length of the `prices` array.\n\n- Space complexity: O(n)\n  The algorithm uses an additional integer array `dp` of the same length as the `prices` array, resulting in a space complexity of O(n).\n  \n# Code\n```java\nclass Solution {\n    public int maxProfit(int[] prices) {\n        if (prices.length <= 1) {\n            return 0;\n        }\n\n        int n = prices.length;\n        int[] dp = new int[n]; \n        dp[0] = 0;\n        int minPrice = prices[0];\n\n        for (int i = 1; i < n; i++) {\n            dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);\n            minPrice = Math.min(minPrice, prices[i]);\n        }\n\n        return dp[n - 1];\n    }\n}\n
['Java']