Several solutions in Python
We only want to buy once, sell once.\n\nBrute force - compare each element, find max diff\n\n    def maxProfit(self, p):\n        n = len(p)\n        max_so_far
We only want to buy once, sell once.\n\n**Brute force** - compare each element, find max diff\n```\n    def maxProfit(self, p):\n        n = len(p)\n        max_so_far = 0\n        \n        for i in range(n):\n            for j in range(i+1,n):\n                max_so_far = max(max_so_far, p[j] - p[i])\n                \n        return max_so_far           \n```\nTime: `O(n^2)`\nSpace: `O(1)`\n\n**Kadane\'s algorithm** \nIf the "profit so far" `cur` becomes negative, start from 0.\nOtherwise add it to current diff `p[i] - p[i-1]` and update `max_so_far` (max profit so far).\n```\n    def maxProfit(self, p):\n        n = len(p)\n        max_so_far, cur = 0, 0\n        \n        for i in range(1,n):\n            cur = max(cur + p[i] - p[i-1], 0)\n            max_so_far = max(cur, max_so_far)\n        return max_so_far           \n```\nTime: `O(n)`\nSpace: `O(1)`\n\n**Comparing with min**\nKeep the `min_so_far` (min element so far) value along with `max_so_far` (max profit so far).\nFind the diff of `p[i]` with `min_so_far` at each step and update `max_so_far` if it exceeds it.\n```\n    def maxProfit(self, p):\n        n = len(p)\n        min_so_far, max_so_far = math.inf, 0\n        \n        for i in range(n):\n            cur = p[i] - min_so_far\n            max_so_far = max(cur, max_so_far)\n            min_so_far = min(min_so_far, p[i])\n        return max_so_far\n```\nTime: `O(n)`\nSpace: `O(1)`\n\n**Slightly more Pythonic or one-liner solution**\n```\ndef maxProfit(self, p):\n        res, min_so_far = 0, math.inf\n        \n        for p1 in p:\n            res, min_so_far = max(res, p1 - min_so_far), min(min_so_far, p1)\n        \n        return res\n```\nTime: `O(n)`\nSpace: `O(1)`
['Dynamic Programming', 'Python', 'Python3']