Segment Tree maintain DP
\nfrom collections import defaultdict\n\nM = 10 ** 9 + 7\n\nclass SegTree:\n    def __init__(self):\n        self.tree = defaultdict(lambda: (0, 0, 0, 0))\n    
```\nfrom collections import defaultdict\n\nM = 10 ** 9 + 7\n\nclass SegTree:\n    def __init__(self):\n        self.tree = defaultdict(lambda: (0, 0, 0, 0))\n        \n    def merge(self, l, r):\n        l_with_f_with_end, l_with_f_without_end, l_without_f_with_end, l_without_f_without_end = l\n        r_with_f_with_end, r_with_f_without_end, r_without_f_with_end, r_without_f_without_end = r\n        r_end_max = max(r_with_f_with_end, r_without_f_with_end)\n        r_without_end_max = max(r_with_f_without_end, r_without_f_without_end)\n        return (max(l_with_f_with_end + r_without_f_with_end, l_with_f_without_end + r_end_max), max(l_with_f_with_end + r_without_f_without_end, l_with_f_without_end + r_without_end_max), max(l_without_f_with_end + r_without_f_with_end, l_without_f_without_end + r_end_max), max(l_without_f_with_end + r_without_f_without_end, l_without_f_without_end + r_without_end_max))\n        \n    def update(self, index, val, i, j, k):\n        if i + 1 == j:\n            self.tree[k] = (val, 0, 0, 0)\n            return\n        mid = (i + j) // 2\n        if index < mid:\n            self.update(index, val, i, mid, 2 * k)\n        else:\n            self.update(index, val, mid, j, 2 * k + 1)\n        self.tree[k] = self.merge(self.tree[2 * k], self.tree[2 * k + 1])\n        \n    def query(self, x, y, i, j, k):\n        if y - 1 < i or x >= j:\n            return (0, 0, 0, 0)\n        if i >= x and j <= y:\n            return self.tree[k]\n        mid = (i + j) // 2\n        return self.merge(self.query(x, y, i, mid, 2 * k), self.query(x, y, mid, j, 2 * k + 1))\n\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n        res = 0\n        segtree = SegTree()\n        for i in range(n):\n            segtree.update(i, nums[i], 0, n, 1)\n        for i, val in queries:\n            segtree.update(i, val, 0, n, 1)\n            res += max(segtree.query(0, n, 0, n, 1))\n            res %= M\n        return res\n```
['Python']