Simple take not_take dp on segment tree beats 100% users
Intuition\nThe intuition is start something like if we had not given any queries, then we are going to perform dp on array storing current index or previous ind
# Intuition\nThe intuition is start something like if we had not given any queries, then we are going to perform dp on array storing current index or previous index . But we are given queries, in each it is not possible to perform dp.\nSo firstly the approach is to build a segment tree, if you are not familiar with segment tree , then you should first learn about segment tree.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSo talking about the condition that no two adjacent elements should be in sum, we are make dp like ,if we take leftmost element and not taking rightmost element then our bit gonna like [1][0] which means 2, similarly taking rightmost and not taking leftmost of partition then we store on seg[ind][0][1] = seg[ind][1] , then for taking both leftmost and rightmost of partition, we will store result in seg[ind][1][1] = seg[ind][3] , so until this time , I had only showed you where we will store in segment tree , now how we will store answer on it. According to the question , we are not suppose to take adjacent elements , means we are not allow to take rightmost element of left partition and leftmost element of right partition. So considering the condition , we will make different combinations , like 01->01 = 01,\n10->01 = 11 (In this case leftmost element of left partition and rightmost element of right partition are considered , dont confuse).\nSimilarly we will store maximum of these combinations.\nThen our answer seg[0] over all 4 combinations.\n\n\n# Complexity\n- Time complexity:\n- Max(nlogn , qlogn)\n\n- Space complexity:\n   o(4*n)\n\n# Code\n```\nint mod=1e9 + 7;\n\nclass Solution {\npublic:\n\n    void build(int ind,int low,int high,vector<int> &nums,vector<vector<int>> &seg){\n        if(low==high){\n            // seg[ind][0][0]=0;\n            // cout<<"vimal"<<endl;\n            seg[ind][0]=0;\n            seg[ind][1]=-1e9;\n            seg[ind][2]=-1e9;\n            seg[ind][3]=nums[low];\n            // seg[ind][0][1]=-1e9;\n            // seg[ind][1][0]=-1e9;\n            // seg[ind][1][1]=nums[low];\n            return;\n        }\n        int mid = low + (high - low)/2;\n        build(2*ind + 1,low,mid,nums,seg);\n        build(2*ind + 2,mid+1,high,nums,seg);\n        seg[ind][0] = max(seg[2*ind + 1][0] + seg[2*ind + 2][0] , max(seg[2*ind + 1][1] + seg[2*ind + 2][0] ,seg[2*ind+1][0] + seg[2*ind+2][2]));\n        seg[ind][1] = max(seg[2*ind + 1][0] + seg[2*ind + 2][1] , max(seg[2*ind + 1][1] + seg[2*ind + 2][1] ,seg[2*ind+1][0] + seg[2*ind+2][3]));\n        seg[ind][2] = max(seg[2*ind + 1][2] + seg[2*ind + 2][0] , max(seg[2*ind + 1][3] + seg[2*ind + 2][0] ,seg[2*ind+1][2] + seg[2*ind+2][2]));\n        seg[ind][3] = max(seg[2*ind + 1][2] + seg[2*ind + 2][1] , max(seg[2*ind + 1][3] + seg[2*ind + 2][1] ,seg[2*ind+1][2] + seg[2*ind+2][3]));\n    }\n\n    void update(int ind,int low,int high,vector<int> &nums,vector<vector<int>> &seg,int k,int val){\n        if(low>k || high<k){\n            return;\n        }\n        if(low == high && high == k){\n           seg[ind][0]=0;\n           seg[ind][3]=val;\n           return ;\n        }\n        int mid=low + (high - low)/2;\n        update(2*ind+1,low,mid,nums,seg,k,val);\n        update(2*ind + 2,mid+1,high,nums,seg,k,val);\n         seg[ind][0] = max(seg[2*ind + 1][0] + seg[2*ind + 2][0] , max(seg[2*ind + 1][1] + seg[2*ind + 2][0] ,seg[2*ind+1][0] + seg[2*ind+2][2]));\n        seg[ind][1] = max(seg[2*ind + 1][0] + seg[2*ind + 2][1] , max(seg[2*ind + 1][1] + seg[2*ind + 2][1] ,seg[2*ind+1][0] + seg[2*ind+2][3]));\n        seg[ind][2] = max(seg[2*ind + 1][2] + seg[2*ind + 2][0] , max(seg[2*ind + 1][3] + seg[2*ind + 2][0] ,seg[2*ind+1][2] + seg[2*ind+2][2]));\n        seg[ind][3] = max(seg[2*ind + 1][2] + seg[2*ind + 2][1] , max(seg[2*ind + 1][3] + seg[2*ind + 2][1] ,seg[2*ind+1][2] + seg[2*ind+2][3]));\n    }\n\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n=nums.size();\n        // vector<vector<vector<int>>> seg(4*n+1,vector<vector<int>> (2,vector<int> (2,-1)));\n        vector<vector<int>> seg(4*n+1,vector<int>(5,0));\n        build(0,0,n-1,nums,seg);\n        int m=queries.size();\n        int ans=0;\n        for(int i=0;i<m;i++){\n            update(0,0,n-1,nums,seg,queries[i][0],queries[i][1]);\n            ans = (ans + max(seg[0][0],max(seg[0][1],max(seg[0][2],seg[0][3]))))%mod;\n        }\n        return ans;\n\n\n    }\n};\n\n\nfor better Understanding :\n\nint mod=1e9 + 7;\n\nclass Solution {\npublic:\n\n    void build(int ind,int low,int high,vector<int> &nums,vector<vector<vector<int>>> &seg){\n        if(low==high){\n            seg[ind][0][0]=0;\n            // cout<<"vimal"<<endl;\n            // seg[ind][0]=0;\n            // seg[ind][1]=-1e9;\n            // seg[ind][2]=-1e9;\n            // seg[ind][3]=nums[low];\n            seg[ind][0][1]=-1e9;\n            seg[ind][1][0]=-1e9;\n            seg[ind][1][1]=nums[low];\n            return;\n        }\n        int mid = low + (high - low)/2;\n        build(2*ind + 1,low,mid,nums,seg);\n        build(2*ind + 2,mid+1,high,nums,seg);\n        seg[ind][0][0] = max(seg[2*ind + 1][0][0] + seg[2*ind + 2][0][0] , max(seg[2*ind + 1][0][1] + seg[2*ind + 2][0][0] ,seg[2*ind+1][0][0] + seg[2*ind+2][1][0]));\n        seg[ind][0][1] = max(seg[2*ind + 1][0][0] + seg[2*ind + 2][0][1] , max(seg[2*ind + 1][0][1] + seg[2*ind + 2][0][1] ,seg[2*ind+1][0][0] + seg[2*ind+2][1][1]));\n        seg[ind][1][0] = max(seg[2*ind + 1][1][0] + seg[2*ind + 2][0][0] , max(seg[2*ind + 1][1][1] + seg[2*ind + 2][0][0] ,seg[2*ind+1][1][0] + seg[2*ind+2][1][0]));\n        seg[ind][1][1] = max(seg[2*ind + 1][1][0] + seg[2*ind + 2][0][1] , max(seg[2*ind + 1][1][1] + seg[2*ind + 2][0][1] ,seg[2*ind+1][1][0] + seg[2*ind+2][1][1]));\n    }\n\n    void update(int ind,int low,int high,vector<int> &nums,vector<vector<vector<int>>> &seg,int k,int val){\n        if(low>k || high<k){\n            return;\n        }\n        if(low == high && high == k){\n           seg[ind][0][0]=0;\n           seg[ind][1][1]=val;\n           return ;\n        }\n        int mid=low + (high - low)/2;\n        update(2*ind+1,low,mid,nums,seg,k,val);\n        update(2*ind + 2,mid+1,high,nums,seg,k,val);\n        //  seg[ind][0] = max(seg[2*ind + 1][0] + seg[2*ind + 2][0] , max(seg[2*ind + 1][1] + seg[2*ind + 2][0] ,seg[2*ind+1][0] + seg[2*ind+2][2]));\n        // seg[ind][1] = max(seg[2*ind + 1][0] + seg[2*ind + 2][1] , max(seg[2*ind + 1][1] + seg[2*ind + 2][1] ,seg[2*ind+1][0] + seg[2*ind+2][3]));\n        // seg[ind][2] = max(seg[2*ind + 1][2] + seg[2*ind + 2][0] , max(seg[2*ind + 1][3] + seg[2*ind + 2][0] ,seg[2*ind+1][2] + seg[2*ind+2][2]));\n        // seg[ind][3] = max(seg[2*ind + 1][2] + seg[2*ind + 2][1] , max(seg[2*ind + 1][3] + seg[2*ind + 2][1] ,seg[2*ind+1][2] + seg[2*ind+2][3]));\n        seg[ind][0][0] = max(seg[2*ind + 1][0][0] + seg[2*ind + 2][0][0] , max(seg[2*ind + 1][0][1] + seg[2*ind + 2][0][0] ,seg[2*ind+1][0][0] + seg[2*ind+2][1][0]));\n        seg[ind][0][1] = max(seg[2*ind + 1][0][0] + seg[2*ind + 2][0][1] , max(seg[2*ind + 1][0][1] + seg[2*ind + 2][0][1] ,seg[2*ind+1][0][0] + seg[2*ind+2][1][1]));\n        seg[ind][1][0] = max(seg[2*ind + 1][1][0] + seg[2*ind + 2][0][0] , max(seg[2*ind + 1][1][1] + seg[2*ind + 2][0][0] ,seg[2*ind+1][1][0] + seg[2*ind+2][1][0]));\n        seg[ind][1][1] = max(seg[2*ind + 1][1][0] + seg[2*ind + 2][0][1] , max(seg[2*ind + 1][1][1] + seg[2*ind + 2][0][1] ,seg[2*ind+1][1][0] + seg[2*ind+2][1][1]));\n    }\n\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n=nums.size();\n        vector<vector<vector<int>>> seg(4*n+1,vector<vector<int>> (2,vector<int> (2,-1)));\n        // vector<vector<int>> seg(4*n+1,vector<int>(5,0));\n        build(0,0,n-1,nums,seg);\n        int m=queries.size();\n        int ans=0;\n        for(int i=0;i<m;i++){\n            update(0,0,n-1,nums,seg,queries[i][0],queries[i][1]);\n            ans = (ans + max(seg[0][0][0],max(seg[0][0][1],max(seg[0][1][0],seg[0][1][1]))))%mod;\n        }\n        return ans;\n\n\n    }\n};\n```
['Dynamic Programming', 'Segment Tree', 'C++']