Square root decomposition + House robber DP
\n#define FULL_BLOCK_SIZE(n) (int(sqrt(n)))\n#define NUM_BLOCKS(n) (((n) + FULL_BLOCK_SIZE(n) - 1) / FULL_BLOCK_SIZE(n))\n#define BLOCK_SIZE(n, blockId) (blockI
```\n#define FULL_BLOCK_SIZE(n) (int(sqrt(n)))\n#define NUM_BLOCKS(n) (((n) + FULL_BLOCK_SIZE(n) - 1) / FULL_BLOCK_SIZE(n))\n#define BLOCK_SIZE(n, blockId) (blockId < NUM_BLOCKS(n) - 1 ? \\\n    FULL_BLOCK_SIZE(n) : (n - (NUM_BLOCKS(n) - 1) * FULL_BLOCK_SIZE(n)))\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n = nums.size();\n        int numB = NUM_BLOCKS(n);\n        vector<tuple<int, int, int, int>> A(numB);\n        for (int i = 0; i < numB; ++i) {\n            int blockSize = BLOCK_SIZE(n, i);\n            get<0>(A[i]) = GetVal(nums, i, 0, blockSize - 2);\n            get<1>(A[i]) = GetVal(nums, i, 1, blockSize - 1);\n            get<2>(A[i]) = GetVal(nums, i, 1, blockSize - 2);\n            get<3>(A[i]) = GetVal(nums, i, 0, blockSize - 1);\n        }\n\n        int ans = 0;\n        for (vector<int>& query : queries) {\n            int pos = query[0];\n            int x = query[1];\n            nums[pos] = x;\n            int blockId = pos / FULL_BLOCK_SIZE(n);\n            int blockSize = BLOCK_SIZE(n, blockId);\n            get<0>(A[blockId]) = GetVal(nums, blockId, 0, blockSize - 2);\n            get<1>(A[blockId]) = GetVal(nums, blockId, 1, blockSize - 1);\n            get<2>(A[blockId]) = GetVal(nums, blockId, 1, blockSize - 2);\n            get<3>(A[blockId]) = GetVal(nums, blockId, 0, blockSize - 1);\n            int res = Query(A);\n            ans = (0L + ans + res) % int(1e9 + 7);\n        }\n        return ans;\n    }\n\nprivate:\n    int GetVal(vector<int>& nums, int blockId, int b, int e) {\n        int n = nums.size();\n        int bIdx = blockId * FULL_BLOCK_SIZE(n);\n        int bSize = BLOCK_SIZE(n, blockId);\n        int yes = 0;\n        int no = 0;\n        int ans = 0;\n        for (int i = b; i <= e; ++i) {\n            if (i == 0) {\n                yes = nums[i + bIdx];\n                no = 0;\n            } else {\n                int newyes = max(nums[i + bIdx], nums[i + bIdx] + no);\n                int newno = max(yes, no);\n                yes = newyes;\n                no = newno;\n            }\n            ans = max({ans, yes, no});\n        }\n        return ans;\n    }\n\n    int Query(vector<tuple<int, int, int, int>>& A) {\n        int n = A.size();\n        int dpA = 0;\n        int dpB = 0;\n        int ans = 0;\n        for (int i = 0; i < n; ++i) {\n            if (i == 0) {\n                dpA = get<0>(A[i]);\n                dpB = get<3>(A[i]);\n            } else {\n                int newdpA = max({get<0>(A[i]), get<0>(A[i]) + dpA, get<2>(A[i]) + dpB});\n                int newdpB = max({get<3>(A[i]), get<3>(A[i]) + dpA, get<1>(A[i]) + dpB});\n                dpA = newdpA;\n                dpB = newdpB;\n            }\n            ans = max(ans, dpB);\n        }\n        return ans;\n    }\n};\n```
[]