DP ISN'T SUPPOSE TO WORK HERE!!! SEGMENT TREES SOLUTION 30X FASTER THAN DP🔥🔥🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nsorry don\'t have time now to write will update when i got the time :-(\n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nsorry don\'t have time now to write will update when i got the time :-(\n\n# Complexity\n- Time complexity: O(n+qLogn)\n\n- Space complexity: O(n+q)\n\n\n# Code\n```\npublic class Solution {\n    private static final long INF = 1_000_000_000_000_000L;\n    private static final long MOD = 1_000_000_007;\n\n    private static class Node {\n        Node left, right;\n        int lo, hi;\n        long[][] selected = new long[2][2];\n\n        Node(int[] nums, int lo, int hi) {\n            this.lo = lo;\n            this.hi = hi;\n            if (lo < hi) {\n                int mid = (lo + hi) / 2;\n                left = new Node(nums, lo, mid);\n                right = new Node(nums, mid + 1, hi);\n                combine();\n            } else {\n                selected[0][0] = 0;\n                selected[0][1] = -INF;\n                selected[1][0] = -INF;\n                selected[1][1] = nums[lo];\n            }\n        }\n\n        private void combine() {\n            selected[0][0] = Math.max(left.selected[0][0] + right.selected[0][0],\n                                     Math.max(left.selected[0][1] + right.selected[0][0],\n                                             left.selected[0][0] + right.selected[1][0]));\n            selected[0][1] = Math.max(left.selected[0][0] + right.selected[0][1],\n                                     Math.max(left.selected[0][1] + right.selected[0][1],\n                                             left.selected[0][0] + right.selected[1][1]));\n            selected[1][0] = Math.max(left.selected[1][0] + right.selected[0][0],\n                                     Math.max(left.selected[1][1] + right.selected[0][0],\n                                             left.selected[1][0] + right.selected[1][0]));\n            selected[1][1] = Math.max(left.selected[1][0] + right.selected[0][1],\n                                     Math.max(left.selected[1][1] + right.selected[0][1],\n                                             left.selected[1][0] + right.selected[1][1]));\n        }\n\n        private void update(int i, long x) {\n            if (i < lo || hi < i) {\n                return;\n            }\n            if (lo == hi) {\n                selected[0][0] = 0;\n                selected[1][1] = x;\n                return;\n            }\n            left.update(i, x);\n            right.update(i, x);\n            combine();\n        }\n    }\n\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        Node segmentTree = new Node(nums, 0, nums.length - 1);\n        long res = 0;\n        for (int[] query : queries) {\n            segmentTree.update(query[0], query[1]);\n            res += Math.max(segmentTree.selected[0][0],\n                           Math.max(segmentTree.selected[0][1],\n                                   Math.max(segmentTree.selected[1][0], segmentTree.selected[1][1])));\n            res %= MOD;\n        }\n        return (int) res;\n    }\n}\n```
['Segment Tree', 'Java']