LC 1425. Constrained Subset Sum

link

using deque:

class Solution {
public:
   
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n=nums.size();
        
        int res=nums[0];
        deque<int> dq;
        for(int i=0;i<n;i++){
            if(dq.size()>0 && dq.front()==i-k-1) dq.pop_front();
            nums[i]+=dq.size()>0?nums[dq.front()]:0;
            res=max(res,nums[i]);
            while(dq.size()>0 && nums[i]>nums[dq.back()]) dq.pop_back();
            if(nums[i]>0) dq.push_back(i);
        }
        return res;
    }
};

using segment tree:

class Solution {
public:
    int seg[100010<<2];
    
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n=nums.size();
        int res=nums[0];
        for(int i=0;i<n;i++){
            int tmp=nums[i]+query(1,1,n+1,i-k+1,i);
            res=max(res,tmp);
            if(tmp>0){
                update(i+1,1,n+1,tmp,1);
            }
        }
        return res;
    }
    
    void update(int uidx, int left, int right, int val, int idx){
        if(left>uidx || right<uidx) return;
        if(left==right) {
            seg[idx]=val;
            return;
        }
        int mid=left+(right-left)/2;
        update(uidx,left,mid,val,idx<<1);
        update(uidx,mid+1,right,val,idx<<1|1);
        seg[idx]=max(seg[idx<<1],seg[idx<<1|1]);
    }
    
    int query(int idx, int left, int right, int qleft, int qright){
        if(qleft>right || qright<left) return 0;
        if(qleft<=left && qright>=right) return seg[idx];
        int mid=left+(right-left)/2;
        int l=query(idx<<1,left,mid,qleft,qright);
        int r=query(idx<<1|1,mid+1,right,qleft,qright);
        return max(l,r);
    }
};