[Python] 2 solutions: Min So Far, Kadane's Algorithm - with Picture - O(1) in Space
\u2714\uFE0F Solution 1: MinSoFar\npython\nclass Solution:\n    def maxProfit(self, prices: List[int]) -> int:\n        n = len(prices)\n        ans = 0\n      
**\u2714\uFE0F Solution 1: MinSoFar**\n```python\nclass Solution:\n    def maxProfit(self, prices: List[int]) -> int:\n        n = len(prices)\n        ans = 0\n        minSoFar = prices[0]\n        for i in range(1, n):\n            ans = max(ans, prices[i] - minSoFar)\n            minSoFar = min(minSoFar, prices[i])\n        return ans\n```\nComplexity:\n- Time: `O(N)`, where `N <= 10^5` is length of `prices` array.\n- Space: `O(1)`\n\n---\n**\u2714\uFE0F Solution 2: Kadane\'s Algorithm**\n- Same with problem **[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)**.\n\n![image](https://assets.leetcode.com/users/images/fc0e41c4-bb24-4d62-9891-0d88f62d49b3_1632370664.418544.png)\n\n\n```python\nclass Solution:\n    def maxProfit(self, prices: List[int]) -> int:\n        n = len(prices)\n        ans = 0\n        curSum = 0\n        for i in range(n-1):\n            curSum += prices[i+1] - prices[i]\n            if curSum < 0:\n                curSum = 0\n            ans = max(ans, curSum)\n        return ans\n```\nComplexity:\n- Time: `O(N)`, where `N <= 10^5` is length of `prices` array.\n- Space: `O(1)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]