Same as House Robber, with one optimization
Disclaimer\nThis soln is giving TLE for multiple people in different languages.\nA better approach would be using Segment Tree.\n\n# Intuition\nThis line remind
# Disclaimer\nThis soln is giving TLE for multiple people in different languages.\nA better approach would be using [Segment Tree](#segment-tree-soln).\n\n# Intuition\nThis line reminds of [house robber](https://leetcode.com/problems/house-robber/description/) problem\n>  maximum sum of a subsequence of nums where no two adjacent elements are selected.\n\n# Approach\n1. for every query, update the appropriate index in nums\n2. Just like [house robber](https://leetcode.com/problems/house-robber/description/) problem, figure out whether to pick current index or not, to maximize the sum.\n\nHowever, this alone will give TLE.\nSo, we need to do something better :\n1. Maintain `dp_incl` & `dp_excl` array, such that for any index I can immediately find out what is max when incuding that index, and max when not including\n2. Now, after updating nums for each query, don\'t loop through entire nums array. Instead, start from index which was changed. All indexes before this you already calculated the max inclusion & exclusion value\n\n\n# Complexity\nn = nums.length\nq = queries.length\n- Time complexity: O(q * n/2)       :: n/2 because on avg, we will loop through half of nums\n- Space complexity: O(2.n)\n\n# Code\n```java\npublic int maximumSumSubsequence(int[] nums, int[][] queries) {\n    var MOD = 1_000_000_007;\n    var n = nums.length;\n    long totalSum = 0; \n\n    var dp_incl = new long[n];     // to track max sum till index i, when including index i\n    var dp_excl = new long[n];     // to track max sum till index i, when excluding index i\n\n    // fill dp initially\n    long incll = 0, excll = 0;\n    for(var i=0; i<n; i++){\n        long newExcl = Math.max(incll, excll);\n        incll = (excll + nums[i]) % MOD;\n        excll = newExcl;\n\n        dp_incl[i] = incll;\n        dp_excl[i] = excll;\n    }\n\n    // now, for each query, update the nums array\n    // and then start calculating incl/excl from the index that was changed\n    for (var query : queries) {\n        int pos = query[0];\n        int val = query[1];\n        nums[pos] = val;\n\n        long incl = 0, excl = 0;\n        if(pos != 0){\n            incl = dp_incl[pos-1];\n            excl = dp_excl[pos-1];\n        }\n\n        for(var i=pos; i<n; i++){\n            long newExcl = Math.max(incl, excl);\n            incl = (excl + nums[i]) % MOD;\n            excl = newExcl;\n\n            dp_incl[i] = incl;\n            dp_excl[i] = excl;\n        }\n\n        long maxSum = Math.max(incl, excl);\n        totalSum = (totalSum + maxSum) % MOD;\n    }\n\n    return (int) totalSum;\n}\n```\n\n# Segment tree soln\n\n```java\n// each node in seg tree will have to maintain 4 values, so that we can apply house robber algo\n// [0][0] : leftmost & rightmost in curr range is not selected\n// [0][1] : leftmost in curr range is not selected, rightmost is selected\n// [0][0] : leftmost in curr range is selected, rightmost is not selected\n// [0][0] : leftmost & rightmost in curr range are both selected\n\nclass Solution {\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        var MOD = 1_000_000_007;\n        var segTree = new Node(nums, 0, nums.length - 1);\n        long res = 0;\n\n        for(var query : queries){\n            segTree.update(query[0], query[1]);\n            res += segTree.getMaxSum();\n            res %= MOD;\n        }\n        return (int)res;\n    }\n}\n\nclass Node {\n    long inf = (long) 1e18;\n    Node l = null, r = null;\n    int lo, hi;\n    long[][] selected = new long[2][2];\n\n    public Node(int[] nums, int lo, int hi){\n        this.lo = lo;\n        this.hi = hi;\n\n        if(lo < hi){\n            var mid = (lo + hi) / 2;\n            l = new Node(nums, lo, mid);\n            r = new Node(nums, mid+1, hi);\n            combine();\n        }\n        else{\n            selected[0][0] = 0;\n            selected[0][1] = -inf;\n            selected[1][0] = -inf;\n            selected[1][1] = nums[lo];  // same as nums[hi]\n        }\n    }\n\n    // house robber algo\n    private void combine(){\n        selected[0][0] = Math.max(l.selected[0][0] + r.selected[0][0], \n                         Math.max(l.selected[0][1] + r.selected[0][0], l.selected[0][0] + r.selected[1][0]));\n        selected[0][1] = Math.max(l.selected[0][0] + r.selected[0][1], \n                         Math.max(l.selected[0][1] + r.selected[0][1], l.selected[0][0] + r.selected[1][1]));\n        selected[1][0] = Math.max(l.selected[1][0] + r.selected[0][0], \n                         Math.max(l.selected[1][1] + r.selected[0][0], l.selected[1][0] + r.selected[1][0]));\n        selected[1][1] = Math.max(l.selected[1][0] + r.selected[0][1], \n                         Math.max(l.selected[1][1] + r.selected[0][1], l.selected[1][0] + r.selected[1][1]));\n    }\n\n    public void update(int idx, long val){\n        if(idx < lo || idx > hi) return;\n\n        // reached root node\n        if(lo == hi){\n            selected[0][0] = 0;\n            selected[1][1] = val;\n            return;\n        }\n\n        l.update(idx, val);\n        r.update(idx, val);\n        combine();\n    }\n\n    public long getMaxSum(){\n        return Math.max(selected[0][0],\n               Math.max(selected[0][1], \n               Math.max(selected[1][0], selected[1][1])));\n    }\n}\n```
['Dynamic Programming', 'Java']