Easy Java Solution | Simple Segment Tree With Four Variables
Intuition\n Describe your first thoughts on how to solve this problem. \nSegment Tree with 5 States\nTo solve the problem of finding the maximum alternating sub
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Segment Tree with 5 States**\nTo solve the problem of finding the maximum alternating subsequence sum efficiently, we use a segment tree. Each node in the segment tree will store five states:\n\n*Max*: The maximum alternating subsequence sum for the segment.\n\n*FirstTakenLastTaken* (fl): Maximum sum of a subsequence where both the first and last elements are taken.\n\n*FirstNotTakenLastNotTaken* (nfnl): Maximum sum of a subsequence where neither the first nor the last elements are taken.\n\n*FirstTakenLastNotTaken* (fnl): Maximum sum of a subsequence where the first element is taken, and the last element is not taken.\n\n*FirstNotTakenLastTaken* (nfl): Maximum sum of a subsequence where the first element is not taken, and the last element is taken.\n\n**Combining Function**\nThis function combines the states to reflect the maximum alternating subsequence sum for their parent node.\n\n# Complexity\n- Time complexity: $$O(n*logq)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(4*n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public class Pair {\n        long max;\n        long fl;\n        long nfnl;\n        long fnl;\n        long nfl;\n\n        Pair(long max, long fl, long nfnl, long fnl, long nfl) {\n            this.max = max;\n            this.fl = fl;\n            this.nfnl = nfnl;\n            this.fnl = fnl;\n            this.nfl = nfl;\n        }\n    }\n\n    public Pair[] tree;\n    public int[] arr;\n    public long MOD = (long)1e9 + 7;\n\n    public void build(int n, int l, int r) {\n        if (l == r) {\n            if (arr[l] < 0) {\n                tree[n] = new Pair(0L, 0L, 0L, 0L, 0l);\n            } else {\n                tree[n] = new Pair(arr[l], arr[l], 0l, 0L, 0L);\n            }\n            return;\n        }\n        int mid = (l + r) >> 1;\n        build(2 * n, l, mid);\n        build(2 * n + 1, mid + 1, r);\n\n        mergeNodes(n);\n    }\n\n    public void update(int n, int l, int r, int idx, int val) {\n        if (l == r) {\n            arr[l] = val;\n            if (arr[l] < 0) {\n                tree[n] = new Pair(0L, 0L, 0L, 0L, 0l);\n            } else {\n                tree[n] = new Pair(arr[l], arr[l], 0l, 0L, 0L);\n            }\n            return;\n        }\n        int mid = (l + r) >> 1;\n        if (idx > mid) {\n            update(2 * n + 1, mid + 1, r, idx, val);\n        } else {\n            update(2 * n, l, mid, idx, val);\n        }\n\n        mergeNodes(n);\n    }\n\n    private void mergeNodes(int n) {\n        long fl = Math.max(tree[2 * n].fnl + tree[2 * n + 1].fl, Math.max(tree[2 * n].fl + tree[2 * n + 1].nfl, tree[2 * n].fnl + tree[2 * n + 1].nfl));\n        long nfnl = Math.max(tree[2 * n].nfnl + tree[2 * n + 1].fnl, Math.max(tree[2 * n].nfl + tree[2 * n + 1].nfnl, tree[2 * n].nfnl + tree[2 * n + 1].nfnl));\n        long fnl = Math.max(tree[2 * n].fnl + tree[2 * n + 1].fnl, Math.max(tree[2 * n].fl + tree[2 * n + 1].nfnl, tree[2 * n].fnl + tree[2 * n + 1].nfnl));        \n        long nfl = Math.max(tree[2 * n].nfnl + tree[2 * n + 1].fl, Math.max(tree[2 * n].nfl + tree[2 * n + 1].nfl, tree[2 * n].nfnl + tree[2 * n + 1].nfl));\n        long max = Math.max(Math.max(fl, nfnl), Math.max(fnl, nfl));\n\n        tree[n] = new Pair(max % MOD, fl, nfnl, fnl, nfl);\n    }\n\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        int n = nums.length;\n        arr = Arrays.copyOf(nums, nums.length);\n        tree = new Pair[4 * n];\n        build(1, 0, n - 1);\n        long ans = 0;\n        for (int[] q : queries) {\n            int idx = q[0];\n            int val = q[1];\n            update(1, 0, n - 1, idx, val);\n            Pair p = tree[1];\n            ans += p.max;\n            ans %= MOD;\n        }\n        return (int)(ans%MOD);\n    }\n}\n```
['Array', 'Segment Tree', 'Java']