Kadane's modified top-down -> bottom-up
Pre requirement for https://leetcode.com/problems/maximum-subarray-sum-after-one-operation/\n\nAs with all dps, we have some choices to make:\n1. skip element @
Pre requirement for https://leetcode.com/problems/maximum-subarray-sum-after-one-operation/\n\nAs with all dps, we have some choices to make:\n1. skip element @ i + use kadane\'s dp/greedy algo to get max subarray sum @ i\n2. keep element @ i + use kadane\'s dp/greedy algo to get max subarray sum @ i\n\nLooks easy, but it\'s quite tricky :-)\n> **Top-down**. If you understand this, the rest is just a convertion to bottom-up\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        @cache\n        def dfs(i, can_remove):\n            if i == 0:\n                dp[i] = nums[i]\n            else:\n                if can_remove:\n                    dp[i] = max(dp[i], dfs(i - 1, False)) # skip element\n                dp[i] = max(dp[i], nums[i] + dfs(i - 1, can_remove), nums[i]) # kadane\n            return dp[i]\n        \n        N = len(nums)\n        dp = [-inf] * N\n        dfs(N - 1, True)\n        return max(dp)\n```\n> **Bottom-up**: remove recursion and use 2d dp array\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        dp = [[-inf] * 2 for _ in range(N)]\n        dp[0][False] = nums[0]\n        for i in range(1, N):\n            for can_remove in [True, False]:\n                if can_remove:\n                    dp[i][can_remove] = max(dp[i][can_remove], dp[i - 1][False])\n                dp[i][can_remove] = max(dp[i][can_remove], nums[i] + dp[i - 1][can_remove], nums[i])\n        return max(v for row in dp for v in row)\n```\n> **Bottom-up**: remove outer `can_remove` loop\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        dp = [[-inf] * 2 for _ in range(N)]\n        dp[0][False] = nums[0]\n        for i in range(1, N):\n            dp[i][True] = max(dp[i][True], dp[i - 1][False])\n            dp[i][True] = max(dp[i][True], nums[i] + dp[i - 1][True], nums[i])\n            dp[i][False] = max(dp[i][False], nums[i] + dp[i - 1][False], nums[i])\n        return max(v for row in dp for v in row)\n```\n> **Bottom-up**: squish `dp[i][True]`\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        dp = [[-inf] * 2 for _ in range(N)]\n        dp[0][False] = nums[0]\n        for i in range(1, N):\n            dp[i][True] = max(dp[i][True], dp[i - 1][False], nums[i] + dp[i - 1][True], nums[i])\n            dp[i][False] = max(dp[i][False], nums[i] + dp[i - 1][False], nums[i])\n        return max(v for row in dp for v in row)\n```\n> **Bottom-up**: split 2d dp array into 2 arrays and use global max at the end\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        dp_true = [-inf] * N\n        dp_false = [-inf] * N\n        dp_false[0] = nums[0]\n        res = nums[0]\n        for i in range(1, N):\n            dp_true[i] = max(dp_true[i], dp_false[i - 1], nums[i] + dp_true[i - 1], nums[i])\n            dp_false[i] = max(dp_false[i], nums[i] + dp_false[i - 1], nums[i])\n            res = max(res, dp_true[i], dp_false[i])\n        return res\n```\n> **Bottom-up**: replace dp arrays with a few variables as `state(i)` depends only on `state(i - 1)`\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        dp_prev_true = dp_true = -inf\n        dp_prev_false = nums[0]\n        dp_false = -inf\n        res = nums[0]\n        for i in range(1, N):\n            dp_true = max(dp_prev_false, nums[i] + dp_prev_true, nums[i])\n            dp_false = max(nums[i] + dp_prev_false, nums[i])\n            dp_prev_true, dp_prev_false = dp_true, dp_false\n            res = max(res, dp_true, dp_false)\n        return res\n```\n> **Bottom-up**: pre-final clean up\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        dp_true = -inf\n        dp_false = nums[0]\n        res = nums[0]\n        for i in range(1, N):\n            dp_true = max(dp_false, nums[i] + dp_true, nums[i])\n            dp_false = max(nums[i] + dp_false, nums[i])\n            res = max(res, dp_true, dp_false)\n        return res\n```\n> **Bottom-up**: pre-final clean up\n```\nclass Solution:\n    def maximumSum(self, nums: List[int]) -> int:\n        N = len(nums)\n        res = dp_true = dp_false = nums[0]\n        for i in range(1, N):\n            res = max(res, dp_true := max(dp_false, nums[i] + dp_true, nums[i]), dp_false := max(nums[i] + dp_false, nums[i]))\n        return res\n```\n\nThe last one, rename `dp_true/false` to `max_subarray_sum_with_removed/max_subarray_sum_without_removed/` and now you got top voted solution with full A-Z intuition and optimizaiton.\n\nNow that you\'ve seen it all!\n**!!! Smash the like button and share it !!!**
['Python', 'Python3']