From O(n^2) to something better
Intuition\n\nAssume first that we just want to compute the ,,maximum sum of a\nsubsequence of nums where no two adjacent elements are selected\'\'.\n\nIt can be
# Intuition\n\nAssume first that we just want to compute the ,,maximum sum of a\nsubsequence of nums where no two adjacent elements are selected\'\'.\n\nIt can be computed iteratively. Let $s_i$ be the answer if the first $i$ element $x_0,\\dots,x_{i-1}$ of $\\text{nums}=[x_0,\\dots, x_{n-1}]$ is considered. Then \n$$\n\\begin{aligned}\n    s_0 & = 0\\\\\n    s_1 & = \\max(0, x_0)\\\\\n    s_{i+1} &= \\max(s_i, s_{i-1}+x_i)\\quad i \\geq 1\n\\end{aligned}\n$$\nThe explanation is that when you consider $x_i$ the $i+1$th element of `nums`, then you have two possibilities. One is to include $x_i$ in the subsequence. Then the maximal sum value is $s_{i-1}+x_i$. Or  not to include $x_i$ and the sum value is the maximal sum value obtained from the first $i$ elements $s_i$. \n\nOne simple observation is that $s$ is a non-decreasing sequence, so when $x_i<0$ then  $s_i \\geq s_{i-1}+x_i$ and we can use $\\max(x_i,0)$, the positive part of $x_i$, everywhere instead of $x_i$. \n\nAnother observation that instead of the sequence $s$ the difference sequence $d_i=s_i-s_{i-1}$ has a simpler recursion relation:\n$$\n\\begin{aligned}\n    d_0 & = 0\\\\\n    d_1 & = \\max(0, x_0)\\\\\n    d_{i+1} &= \\max(s_i, s_{i-1}+x_i)-s_i\n    \\\\&=\\max(0, x_i-(s_i-s_{i-1}))\\\\&=\\max(0,x_i-d_{i})\\quad i \\geq 1\n\\end{aligned}    \n$$\n\nNow suppose that the array $d$ is already computed and we modify one element of `nums`. Then the $d$ array will change at some places. If the element changed is $x_i$ to $x\'_i$ then the first $i$ elment of $d$ wont change. One can easily compute the changes in $d$ and once we find an index $j\\geq i$ such that $d$ does not change at $j$ there won\'t be any changes after $j$.\n\nFor a random query sequence the average number of changes in $d$ is less than 2 (very close to 1). You can play with it by commenting out the last print.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ndef max_subseq(nums):\n    a, b = 0, 0\n    for num in nums:\n        a, b = b, max(b, a+num)\n    return b\n\ndef max_subseq2(nums):\n    d = 0\n    total = 0\n    for num in nums:\n        if num > d:\n            d = num-d\n        else:\n            d = 0\n        total += d\n    return total\n\n\nP = 1_000_000_007\n\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        for i, num in enumerate(nums):\n            if num < 0:\n                nums[i] = 0\n\n            \n        total = 0\n        for pos, val in queries:\n            nums[pos] = max(val, 0)\n            sum_val = max_subseq(nums) \n            sum_val2 = max_subseq2(nums)\n            total += sum_val\n            print(f"{total=}, {sum_val=}, {sum_val2=} ")\n        return total\n\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        for i, num in enumerate(nums):\n            if num < 0:\n                nums[i] = 0\n\n        diffs = [0]*len(nums)\n        d = 0\n        sum_val = 0\n        for pos, num in enumerate(nums):\n            if num > d:\n                d = num-d\n            else:\n                d = 0\n            diffs[pos] = d\n            sum_val += d\n\n        total = 0\n        inner_loop = 0\n        for pos, val in queries:\n            nums[pos] = max(val, 0)\n            d = diffs[pos-1] if pos > 0 else 0\n            \n            pos0 = pos\n            while (\n                pos < len(diffs) and \n                (d := nums[pos]-d if nums[pos] > d else 0) != diffs[pos]\n            ):\n                sum_val += d-diffs[pos]\n                diffs[pos] = d\n                pos += 1\n\n            inner_loop += pos-pos0\n            total = (total + sum_val) % P\n            # print(f"{sum_val=}, {total=}\\n\\t{diffs=}")\n        # print(f"{inner_loop/len(queries)=}")\n        return total\n```
['Python3']