[Python] O(n) dynamic programming solution, explained
Classical dynamic programming problem. Let dp[i] be a maximum profit we can have if we sell stock at i-th moment of time. Then we can get, that dp[i+1] = max(dp
Classical dynamic programming problem. Let `dp[i]` be a maximum profit we can have if we sell stock at `i`-th moment of time. Then we can get, that `dp[i+1] = max(dp[i] + q, q)`, where `q = nums[i+1] - nums[i]`, we have two choices, either we just buy and immeditely sell and get `q` gain, or we use `dp[i] + q` to merge two transactions. \n\nNote now, that we do not really need to keep all `dp` array, but we can keep only last state.\n\n**Complexity**: time complexity is `O(n)`, space complexity is `O(1)`.\n\n```\nclass Solution:\n    def maxProfit(self, nums):\n        ans, dp = 0, 0\n        for i in range(0, len(nums)-1):\n            q = nums[i+1] - nums[i]\n            dp = max(dp + q, q)\n            ans = max(ans, dp)\n        return ans\n```\n\n**PS** Look also my solutions to similar problems: \nBest Time to Buy and Sell Stock III\nhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/794633/Python-O(n)-solution-with-optimization-explained\nBest Time to Buy and Sell Stock with Cooldown\nhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/761720/Python-dp-O(n)-solution-using-differences-explained\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']