Java Solution | Dynamic Programming | Easy to Understand | Beats 100%
Intuition\nThe problem is asking to find the maximum sum of a non-adjacent subsequence in an array after each query. The intuition here is to use a dynamic prog
# Intuition\nThe problem is asking to find the maximum sum of a non-adjacent subsequence in an array after each query. The intuition here is to use a dynamic programming approach to find the maximum sum of a non-adjacent subsequence in the array after each query.\n\n# Approach\n1. For each query, update the array at the index specified by the query.\n1. Call the findMaxSum function to find the maximum sum of a non-adjacent subsequence in the updated array.\n1. Add the maximum sum to the answer, taking the modulo of 1_000_000_007 to prevent overflow.\n1. The findMaxSum function uses a dynamic programming approach to find the maximum sum of a non-adjacent subsequence in the array. It maintains two variables, incl and excl, to keep track of the maximum sum including the current element and the maximum sum excluding the current element, respectively.\n1. Return the maximum of incl and excl.\n\n# Complexity\n- Time complexity:\nThe time complexity is $$O(n*q)$$, where n is the length of the array and q is the number of queries. For each query, we are finding the maximum sum of a non-adjacent subsequence in the array, which takes O(n) time.\n\n- Space complexity:\nThe space complexity is $$O(1)$$, as we are using only a constant amount of space.\n\n# Code\n```java\nclass Solution {\n    \n    static final int MOD = 1_000_000_007;\n    \n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        int ans = 0;\n        int n = nums.length;\n\n        for (int[] query : queries) {\n            nums[query[0]] = query[1];\n\n            ans = (ans + findMaxSum(nums, n)) % 1_000_000_007;\n        }\n        return ans;\n    }\n    \n    public static int findMaxSum(int[] arr, int n) {\n        int incl = arr[0];\n        int excl = 0;\n        int exclNew;\n        int i;\n\n        for (i = 1; i < n; i++) {\n            // Current max excluding i\n            exclNew = Math.max(incl, excl);\n\n            // Current max including i\n            incl = excl + arr[i];\n            excl = exclNew;\n        }\n\n        // Return max of incl and excl\n        return Math.max(incl, excl);\n    }\n    \n}\n```
['Array', 'Dynamic Programming', 'Java']