Maximum Sum Subsequence with Queries
Intuition\n\nThe problem requires updating elements in an array based on given queries and calculating the maximum sum of a subsequence where no two elements ar
# Intuition\n\nThe problem requires updating elements in an array based on given queries and calculating the maximum sum of a subsequence where no two elements are adjacent. This is a variation of the "*House Robber*" problem where we need to skip adjacent elements to maximize the sum.\n\n# Approach\n\n1. **Update the Array:** For each query, update the element in the nums array at the specified index.\n2. **Edge Case Handling:** If the length of the array is 1, directly add the maximum of the single element or 0 to the answer.\n3. **Dynamic Programming:**\ni. Use two variables, twoBack and oneBack, to keep track of the maximum sums up to the previous two indices.\nii. Iterate through the array and update these variables to find the maximum sum subsequence up to the current index while ensuring no two elements are adjacent.\n4. **Update the Answer:** After processing each query, update the final answer with the calculated maximum sum subsequence.\n\n# Complexity\n-  **Time complexity:**\n\n- - Updating the array and calculating the maximum sum subsequence for each query both take O(n) time.\n- - Given \'m\' queries, the total time complexity is O(m\u22C5n).\n\n- **Space complexity:**\n- - The algorithm uses a constant amount of extra space beyond the input data, hence the space complexity is O(1).\n\n# Code\n```\nclass Solution {\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        int ans = 0; // Initialize the final answer to 0\n        int len = nums.length; // Get the length of the input array\n        int mod = (int)1e9 + 7; // Define the modulo value to handle large sums\n\n        for (int[] query : queries) {\n            // Update the value in the nums array based on the current query\n            nums[query[0]] = query[1];\n\n            // Handle the edge case where the length of nums is 1\n            if (len == 1) {\n                ans = (ans + Math.max(nums[0], 0)) % mod;\n                continue;\n            }\n\n            // Initialize twoBack and oneBack for the dynamic programming approach\n            int twoBack = Math.max(nums[0], 0); // Maximum sum up to index 0\n            int oneBack = Math.max(twoBack, nums[1]); // Maximum sum up to index 1\n\n            // Iterate through the array starting from index 2\n            for (int i = 2; i < len; i++) {\n                int cur = Math.max(oneBack, twoBack + Math.max(nums[i], 0)); // Calculate the current maximum sum\n                twoBack = oneBack; // Update twoBack to the previous oneBack\n                oneBack = cur; // Update oneBack to the current maximum sum\n            }\n\n            // Update the final answer with the current maximum sum, taking modulo to handle large sums\n            ans = (ans + oneBack) % mod;\n        }\n\n        return ans; // Return the final computed answer\n    }\n}\n\n```
['Java']