Red herrings are delicious
Intuition \nWe start by getting the red herring out of the way. The "no two adjacent elements are selected" is just there to confuse us. Let\'s solve the "simpl
# Intuition \nWe start by getting the red herring out of the way. The "**no two adjacent elements are selected**" is just there to confuse us. Let\'s solve the "simpler" problem without that condition, and then add it back at the end.\n\nGiven a sequence of numbers, there is a simple way of finding the best subsequence with maximum sum. Indeed, in any such best subsequence we either use or don\'t use the last element (for example, if it is negative) so that:\n```\nmax_subseq_sum(nums) = max(max_subseq_sum(nums[:-1])+nums[-1], max_subseq_sum(nums[:-1]))\n```\nSo if we know that best subsequence sum for **nums** without the last element, then this is a single command to compute the best subsequence sum for the full sequence. A simple loop can now compute this best subsequence sum in $O(|nums|)$, and a total $O(|nums|*|queries|)$ for the full solution.\n\nTrying to improve this running time, while we can\'t probably get rid of the $|queries|$ part, since we must go over each query, the $|nums|$ part can be much improved. Indeed, a lot of the computation at each query iteration is probably very similar - in particular, if the element that we changed is near the end of the sequence, then almost all the computation is the same. \n\nOn the other hand, if the element is at the beginning, this is not so trivial anymore, because we don\'t know when it affects a maximum subsequence sum. However, the interesting thing here, that we can reverse the beginning and the end of the sequence! So maybe we can compute these subsequence sums from both sides, and use it for faster query iterations.\n\nBut then, what if the element is in the middle? This is still not a problem since we can "begin" summing from both ends towards the middle.\n\nThinking about this behaviour a little, we can reach the conclusion that if we keep track of "several" ways of computing the sums, from all sorts of directions, it might be possible to (1) quickly compute the best subsequence sum after each query, and (2) quickly update the sum data needed for the next queries.\n\nIn a more formal way of thinking, this all comes down to the fact that \n$sum(A\\sqcup B) = sum(A)+sum(B)$.\nThis divide and conquer approach shows that we can sum up from all sorts of directions, and if for example we changed an element in the $A$ set, and we already computed the new sum of its elements, it is easy to compute the sum of all of $A\\sqcup B$, since we already know $sum(B)$.\n\nWith this idea, we should construct some binary tree partition of the sequence and then use the natural $O(\\log(n))$ time to update and query this structure.\n\n## The red herring\nSuppose that we have the sequence: $[-1, 5, 6, 3]$. We can split it into $[-1,5]$ and $[6,3]$ where their maximal subsequence sums are $5$ and $9$ respectively, and therefore the maximal sum of the entire sequence is $14=5+9$.\n\nIf the subsequence cannot have two consecutive elements, then we just need to keep track of maximal sums where the edges are either in or not in the subsequence.\nFor example, the $[-1,5]$ has maximal subsequence sum of $5$, but if we require it to not have the right end point $5$, the best subsequence sum is $0$. Similarly, the $[6,3]$ best subsequence sum without the left end point is $3$. All in all we have, our new subsequence sum function should satisfy:\n$subseqsum([-1,5,6,3]) = max(subseqsum([-1])+subseqsum([6,3]) , subseqsum([-1,5]) + subseqsum([3]))$.\nMore generally, for each consecutive subsequence we should keep track over sums of four valid subsequences: whether the left endpoint can appear or not $\\times$ whether the right end point can appear or not.\n\n\n# The algorithm\nWith the ideas above, we construct a tree where each node corresponds to a consecutive subsequence of the original sequence, and a parent node corresponds to the union of its children. For example, with $[-1,5,6,3]$ we will have:\n![image.png](https://assets.leetcode.com/users/images/c8e83b75-232d-42cb-a36f-fe97c1c877b0_1723657124.0366402.png)\n\nFor each node we will keep four max subsequence sums for valid subsequences of it corresponding subsequence (these are 3 subsequences in a sequence!):\n```python []\nnode[OO]\nnode[OX]\nnode[XO]\nnode[XX]\n```\nWhere $X$ marks if we can use the corresponding end point at the position of the $X$. For a leaf node $[k]$ we have that ```node[XX] = max(0,k)```, and the rest are zero. For a parent node we have\n```python []\n    parent[OO] = max(left[OX] + right[OO], left[OO] + right[XO])\n    parent[OX] = max(left[OX] + right[OX], left[OO] + right[XX])\n    parent[XO] = max(left[XX] + right[OO], left[XO] + right[XO])\n    parent[XX] = max(left[XX] + right[OX], left[XO] + right[XX])\n```\n\nTo keep the tree easy to handle, we can add zeroes to the end of the sequence, making it of size power of 2, so we can build a full binary tree.\n\nThe max sum of a valid subsequence is then simply ```root[XX]```.\n\nUpdating the tree is simply starting at the corresponding leaf, and then updating all the way up to the roots, for a total of $O(\\log(n))$ steps.\n\nSpecifically, in my code I implemented the tree inside an array, where the leaves sit at the odd integers, namely 1 mod 2, their parent at indices which are 2 mod 4, their parent at 4 mod 8 etc (as can be seen in the picture above).\n\n# Complexity\n\n- **Space complexity**:\n  Padding the sequence with zeros, increase it at most by a factor of 2, and the tree above it has 2 times the size of this new sequence. So while we add some "unnecessary" space for simplicity, it is still $O(|nums|)$\n\n- **Time complexity**: Creating the tree takes $O(|nums|)$ steps, and each tree update is $O(\\log(|nums|))$, so we get a total of $O(|nums| + |queries|\\cdot \\log|nums|)$\n\n# Code\n```python []\nOO = 0\nOX = 1\nXO = 2\nXX = 3\n\nMOD = 1000000007\n\ndef lsb(k):\n    return k & (-k)\n\nzeroes = [0, 0, 0, 0]\n\nclass Solution(object):\n\n    def maximumSumSubsequence(self, nums, queries):\n        """\n        :type nums: List[int]\n        :type queries: List[List[int]]\n        """\n        n = len(nums)\n\n        # Initializing the tree\n        tree_root_index = 1 << (n-1).bit_length()\n        total_sums = [zeroes for _ in range(2 * tree_root_index + 1)]\n\n        for i in range(n):\n            total_sums[2 * i + 1] = [0, 0, 0, max(0, nums[i])]\n\n        m = n\n        p = 1\n        while m > 1:\n            m = (m+1) >> 1\n            for i in range(m):\n                index = (2 * i + 1)*2*p\n                left = total_sums[index - p]\n                right = total_sums[index + p]\n                total_sums[index] = [\n                    max(left[OX] + right[OO], left[OO] + right[XO]),\n                    max(left[OX] + right[OX], left[OO] + right[XX]),\n                    max(left[XX] + right[OO], left[XO] + right[XO]),\n                    max(left[XX] + right[OX], left[XO] + right[XX]),\n                ]\n            p = p << 1\n\n        # Running the queries\n        total_sum = 0\n        for pos, x in queries:\n            index = 2 * pos + 1\n            total_sums[index] = [0, 0, 0, max(0, x)]\n\n            # Updating the tree\n            p = 1\n            while index != tree_root_index:\n\n                if lsb(index + p) == 2*p:\n                    index += p\n                else:\n                    index -= p\n\n                left = total_sums[index - p]\n                right = total_sums[index + p]\n                mid = [\n                    max(left[OX] + right[OO], left[OO] + right[XO]),\n                    max(left[OX] + right[OX], left[OO] + right[XX]),\n                    max(left[XX] + right[OO], left[XO] + right[XO]),\n                    max(left[XX] + right[OX], left[XO] + right[XX]),\n                ]\n                if total_sums[index] == mid:\n                    break\n                total_sums[index] = mid\n\n                p = p << 1\n\n            # Updating total sum\n            total_sum += total_sums[tree_root_index][XX]\n\n        return total_sum % MOD\n```\n\n# Counting sequence\n\nThe word **sequence** appeared 38 times in this post.
['Python']