[Python] Square Root Decomposition. No Segment Tree. DP of DP. O(M√N). Pass. With explanation.
Intuition\n Describe your first thoughts on how to solve this problem. \nJust didn\'t want to use Segemnt Tree. haha.\nI reccomend to use Seqment Tree. But know
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nJust didn\'t want to use Segemnt Tree. haha.\nI reccomend to use Seqment Tree. But knowing Square Root Decomposition approach must be nice too.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSeparate `nums` into \u221AN blocks. Then each block will have \u221AN elemnts.\nWhen updating, find the block cointains i-th element and update all elements inside the block by DP. This only takes O(\u221AN) time.\n\nAnd then, calculate sum of blocks by DP. This also takes O(\u221AN) time.\n\nSo that for each query, we need O(\u221AN) + O(\u221AN) = O(\u221AN) time.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(M\u221AN) where N = len(nums) and M = len(queries)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) since we have O(\u221AN) blocks and each block has O(\u221AN) elements at most\n\n# Code\n```\nimport math\nMOD = 1000000007\nLAST = 1\nSECOND_LAST, LAST = 0, 1\nUSE_FIRST, SKIP_FIRST = 0, 1\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n        sqrtn = math.ceil(math.sqrt(n))\n\n        blocks = [[] for _ in range(sqrtn)]        \n        for i in range(n):\n            blocks[i//sqrtn].append(nums[i])\n\n        def dp_in_block(ar, start_i): # DP in a block. Returns the last two\n            if len(ar) == 0 or (len(ar) == 1 and start_i == 1):\n                return 0, 0\n            elif len(ar) == 1:\n                return 0, max(0, ar[0])\n            elif len(ar) == 2 and start_i == 1:\n                return 0, max(0, ar[1])\n\n            dp0 = max(0, ar[start_i])\n            dp1 = max(0, ar[start_i], ar[start_i+1])\n\n            for i in range(start_i+2, len(ar)):\n                dp0, dp1 = dp1, max(0, dp1, dp0+ar[i])\n            \n            return dp0, dp1\n\n        # Cache for block sum Cache[block_i][use first or not] = last two dp elements\n        cache = []\n        for i in range(sqrtn):\n            last_two = dp_in_block(blocks[i], 0)\n            last_two_when_skip_first = dp_in_block(blocks[i], 1)\n            cache.append((last_two, last_two_when_skip_first))\n\n        ans = 0\n        for (index, num) in queries:\n            block_i = index // sqrtn\n            blocks[block_i][index%sqrtn] = num\n\n            last_two = dp_in_block(blocks[block_i], 0)\n            last_two_when_skip_first = dp_in_block(blocks[block_i], 1)\n            cache[block_i] = (last_two, last_two_when_skip_first)\n\n            if len(cache) == 1:\n                ans = (ans + max(cache[0][0])) % MOD\n            else:\n                # DP of blocks to get sum (by using cache)\n                dp0, dp1 = cache[0][0]\n                for block_i in range(1, len(cache)):\n                    dp0tmp = max(dp1 + cache[block_i][SKIP_FIRST][SECOND_LAST], dp0 + cache[block_i][USE_FIRST][SECOND_LAST])\n                    dp1tmp = max(dp1 + cache[block_i][SKIP_FIRST][LAST],        dp0 + cache[block_i][USE_FIRST][LAST])\n                    dp0, dp1 = dp0tmp, dp1tmp\n            \n                ans = (ans + max(dp0, dp1)) % MOD\n\n        return ans % MOD\n\n\n```
['Dynamic Programming', 'Python3']