Clear code using Segement Tree - Java
For each segemented range, we only consider if the start element and end element are selected to form the subsequence.\n# Code\n\nclass Solution {\n    class Cu
For each segemented range, we only consider if the start element and end element are selected to form the subsequence.\n# Code\n```\nclass Solution {\n    class CustomNode {\n        CustomNode left, right;\n        int start, end;\n        // containStart means the subsequence - [start, end] contains the element on index \'start\', but not contains the element on index \'end\'\n        // containEnd means the subsequence - [start, end] don\'t contain the element on index \'start\', but contains the element on index \'end\'\n        // notContain means the subsequence - [start, end] don\'t contain both the elements on index \'start\' and \'end\'\n        // containBoth means the subsequence - [start, end] contains both the elements on index \'start\' and \'end\'\n        long containStart, containEnd, notContain, containBoth;\n\n        CustomNode(int start, int end) {\n            this.start = start;\n            this.end = end;\n            this.containStart = 0;\n            this.containEnd = 0;\n            this.notContain = 0;\n            this.containBoth = 0;\n        }\n\n        public void update(int index, int val) {\n            if (index > end || index < start) return;\n            if (start == end) {\n                containStart = 0;\n                containEnd = 0;\n                notContain = 0;\n                containBoth = val;\n                return;\n            }\n            int mid = start + (end - start) / 2;\n            if (left == null) {\n                left = new CustomNode(start, mid);\n                right = new CustomNode(mid + 1, end);\n            }\n            left.update(index, val);\n            right.update(index, val);\n            containStart = getMaxContainStart(left, right);\n            containEnd = getMaxContainEnd(left, right);\n            notContain = getMaxNotContain(left, right);\n            containBoth = getMaxContainBoth(left, right);\n        }\n\n        public long query() {\n            long ret = 0;\n            ret = Math.max(ret, containStart);\n            ret = Math.max(ret, containEnd);\n            ret = Math.max(ret, containBoth);\n            ret = Math.max(ret, notContain);\n            return ret;\n        }\n\n        private long getMaxContainBoth(CustomNode left, CustomNode right) {\n            long ret = Long.MIN_VALUE;\n            ret = Math.max(ret, left.containStart + right.containEnd);\n            ret = Math.max(ret, left.containStart + right.containBoth);\n            ret = Math.max(ret, left.containBoth + right.containEnd);\n            return ret;\n        }\n\n        private long getMaxNotContain(CustomNode left, CustomNode right) {\n            long ret = Long.MIN_VALUE;\n            ret = Math.max(ret, left.containEnd + right.notContain);\n            ret = Math.max(ret, left.notContain + right.notContain);\n            ret = Math.max(ret, left.notContain + right.containStart);\n            return ret;\n        }\n\n        private long getMaxContainEnd(CustomNode left, CustomNode right) {\n            long ret = Long.MIN_VALUE;\n            ret = Math.max(ret, left.containEnd + right.containEnd);\n            ret = Math.max(ret, left.notContain + right.containEnd);\n            ret = Math.max(ret, left.notContain + right.containBoth);\n            return ret;\n        }\n\n        private long getMaxContainStart(CustomNode left, CustomNode right) {\n            long ret = Long.MIN_VALUE;\n            ret = Math.max(ret, left.containStart + right.containStart);\n            ret = Math.max(ret, left.containStart + right.notContain);\n            ret = Math.max(ret, left.containBoth + right.notContain);\n            return ret;\n        }\n    }\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        int n = nums.length;\n        CustomNode root = new CustomNode(0, n - 1);\n        for (int i = 0; i < n; i++) {\n            int num = nums[i];\n            root.update(i, num);\n        }\n        long ret = 0;\n        for (int i = 0; i < queries.length; i++) {\n            int[] query = queries[i];\n            root.update(query[0], query[1]);\n            ret += root.query();\n        }\n        return (int) (ret % ((int) 1e9 + 7));\n    }\n}\n```
['Java']