🔥Most Optimized ||🌟Kadane's Algorithm || Java || C++ || Python || Rust || JavaScript
Intuition\nThe problem aims to find the maximum profit that can be obtained by buying and selling a stock. The given solution seems to follow a simple approach 
# Intuition\nThe problem aims to find the maximum profit that can be obtained by buying and selling a stock. The given solution seems to follow a simple approach of iterating through the prices, keeping track of the minimum buying price, and updating the profit whenever a higher selling price is encountered.\n\n\n![image.png](https://assets.leetcode.com/users/images/c82e3ed3-2b69-48f7-aff2-3df8e0696db9_1710429502.6036055.png)\n# Approach\n1. Initialize variables `buy` with the first element of the prices array and `profit` as 0.\n2. Iterate through the prices starting from the second element.\n3. Update the `buy` variable if the current price is lower than the current buying price.\n4. Update the `profit` if the difference between the current price and the buying price is greater than the current profit.\n5. Return the final profit.\n# Kadane\'s Algorithm\n\nKadane\'s Algorithm is a dynamic programming technique used to find the maximum subarray sum in an array of numbers. The algorithm maintains two variables: `max_current` represents the maximum sum ending at the current position, and `max_global` represents the maximum subarray sum encountered so far. At each iteration, it updates `max_current` to include the current element or start a new subarray if the current element is larger than the accumulated sum. The `max_global` is updated if `max_current` surpasses its value.\n\n# Relating with the Approach\n\nIn the provided approach for finding the maximum profit in stock prices, the algorithm can be seen as a variation of Kadane\'s Algorithm. Instead of finding the maximum subarray sum directly, it focuses on finding the maximum positive difference between consecutive elements (prices) in the array. \n\nHere\'s how the approach relates to Kadane\'s Algorithm:\n\n1. **Initialization:**\n   - In Kadane\'s Algorithm, `max_current` and `max_global` are initialized to the first element of the array.\n   - In the stock profit approach, `buy` is initialized with the first element of the prices array, and `profit` is initialized to 0.\n\n2. **Iteration:**\n   - Kadane\'s Algorithm iterates through the array, updating `max_current` based on the current element\'s value and deciding whether to start a new subarray.\n   - The stock profit approach iterates through the prices array, updating `buy` when a lower price is encountered and treating the difference between the current price and `buy` as a potential profit.\n\n3. **Comparison and Update:**\n   - Kadane\'s Algorithm compares and updates `max_current` and `max_global` at each iteration.\n   - The stock profit approach compares and updates `profit` whenever a positive difference between the current price and `buy` exceeds the current profit.\n# Complexity\n- Time complexity: $$O(n)$$, where $$n$$ is the length of the prices array. The algorithm iterates through the array once.\n- Space complexity: $$O(1)$$, as only a constant amount of extra space is used.\n\n# Code\n```java []\nclass Solution {\n    public int maxProfit(int[] prices) {\n        int buy = prices[0];\n        int profit = 0;\n        for (int i = 1; i < prices.length; i++) {\n            if (prices[i] < buy) {\n                buy = prices[i];\n            } else if (prices[i] - buy > profit) {\n                profit = prices[i] - buy;\n            }\n        }\n        return profit;\n    }\n}\n```\n```c++ []\nclass Solution {\npublic:\n    int maxProfit(std::vector<int>& prices) {\n        int buy = prices[0];\n        int profit = 0;\n        for (int i = 1; i < prices.size(); i++) {\n            if (prices[i] < buy) {\n                buy = prices[i];\n            } else if (prices[i] - buy > profit) {\n                profit = prices[i] - buy;\n            }\n        }\n        return profit;\n    }\n};\n```\n```python []\nclass Solution:\n    def maxProfit(self, prices):\n        buy = prices[0]\n        profit = 0\n        for i in range(1, len(prices)):\n            if prices[i] < buy:\n                buy = prices[i]\n            elif prices[i] - buy > profit:\n                profit = prices[i] - buy\n        return profit\n```\n```rust []\nimpl Solution {\n    pub fn max_profit(prices: Vec<i32>) -> i32 {\n        let mut buy = prices[0];\n        let mut profit = 0;\n        for i in 1..prices.len() {\n            if prices[i] < buy {\n                buy = prices[i];\n            } else if prices[i] - buy > profit {\n                profit = prices[i] - buy;\n            }\n        }\n        profit\n    }\n}\n```\n```javascript []\nclass Solution {\n    maxProfit(prices) {\n        let buy = prices[0];\n        let profit = 0;\n        for (let i = 1; i < prices.length; i++) {\n            if (prices[i] < buy) {\n                buy = prices[i];\n            } else if (prices[i] - buy > profit) {\n                profit = prices[i] - buy;\n            }\n        }\n        return profit;\n    }\n}\n```\n\n![3 upvote.png](https://assets.leetcode.com/users/images/61340855-1311-4dfa-8baa-7588848a6316_1710321564.2869911.png)\n
['Python', 'C++', 'Java', 'Rust', 'JavaScript']