Welcome to Subscribe On Youtube

1425. Constrained Subsequence Sum

Description

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

 

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

 

Constraints:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

Solutions

  • class Solution {
        public int constrainedSubsetSum(int[] nums, int k) {
            int n = nums.length;
            int[] dp = new int[n];
            int ans = Integer.MIN_VALUE;
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = 0; i < n; ++i) {
                if (!q.isEmpty() && i - q.peek() > k) {
                    q.poll();
                }
                dp[i] = Math.max(0, q.isEmpty() ? 0 : dp[q.peek()]) + nums[i];
                while (!q.isEmpty() && dp[q.peekLast()] <= dp[i]) {
                    q.pollLast();
                }
                q.offer(i);
                ans = Math.max(ans, dp[i]);
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int constrainedSubsetSum(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> dp(n);
            int ans = INT_MIN;
            deque<int> q;
            for (int i = 0; i < n; ++i) {
                if (!q.empty() && i - q.front() > k) q.pop_front();
                dp[i] = max(0, q.empty() ? 0 : dp[q.front()]) + nums[i];
                ans = max(ans, dp[i]);
                while (!q.empty() && dp[q.back()] <= dp[i]) q.pop_back();
                q.push_back(i);
            }
            return ans;
        }
    };
    
  • class Solution:
        def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
            n = len(nums)
            dp = [0] * n
            ans = -inf
            q = deque()
            for i, v in enumerate(nums):
                if q and i - q[0] > k:
                    q.popleft()
                dp[i] = max(0, 0 if not q else dp[q[0]]) + v
                while q and dp[q[-1]] <= dp[i]:
                    q.pop()
                q.append(i)
                ans = max(ans, dp[i])
            return ans
    
    
  • func constrainedSubsetSum(nums []int, k int) int {
    	n := len(nums)
    	dp := make([]int, n)
    	ans := math.MinInt32
    	q := []int{}
    	for i, v := range nums {
    		if len(q) > 0 && i-q[0] > k {
    			q = q[1:]
    		}
    		dp[i] = v
    		if len(q) > 0 && dp[q[0]] > 0 {
    			dp[i] += dp[q[0]]
    		}
    		for len(q) > 0 && dp[q[len(q)-1]] < dp[i] {
    			q = q[:len(q)-1]
    		}
    		q = append(q, i)
    		ans = max(ans, dp[i])
    	}
    	return ans
    }
    
  • function constrainedSubsetSum(nums: number[], k: number): number {
        const q = new Deque<number>();
        const n = nums.length;
        q.pushBack(0);
        let ans = nums[0];
        const f: number[] = Array(n).fill(0);
        for (let i = 0; i < n; ++i) {
            while (i - q.frontValue()! > k) {
                q.popFront();
            }
            f[i] = Math.max(0, f[q.frontValue()!]!) + nums[i];
            ans = Math.max(ans, f[i]);
            while (!q.isEmpty() && f[q.backValue()!]! <= f[i]) {
                q.popBack();
            }
            q.pushBack(i);
        }
        return ans;
    }
    
    class Node<T> {
        value: T;
        next: Node<T> | null;
        prev: Node<T> | null;
    
        constructor(value: T) {
            this.value = value;
            this.next = null;
            this.prev = null;
        }
    }
    
    class Deque<T> {
        private front: Node<T> | null;
        private back: Node<T> | null;
        private size: number;
    
        constructor() {
            this.front = null;
            this.back = null;
            this.size = 0;
        }
    
        pushFront(val: T): void {
            const newNode = new Node(val);
            if (this.isEmpty()) {
                this.front = newNode;
                this.back = newNode;
            } else {
                newNode.next = this.front;
                this.front!.prev = newNode;
                this.front = newNode;
            }
            this.size++;
        }
    
        pushBack(val: T): void {
            const newNode = new Node(val);
            if (this.isEmpty()) {
                this.front = newNode;
                this.back = newNode;
            } else {
                newNode.prev = this.back;
                this.back!.next = newNode;
                this.back = newNode;
            }
            this.size++;
        }
    
        popFront(): T | undefined {
            if (this.isEmpty()) {
                return undefined;
            }
            const value = this.front!.value;
            this.front = this.front!.next;
            if (this.front !== null) {
                this.front.prev = null;
            } else {
                this.back = null;
            }
            this.size--;
            return value;
        }
    
        popBack(): T | undefined {
            if (this.isEmpty()) {
                return undefined;
            }
            const value = this.back!.value;
            this.back = this.back!.prev;
            if (this.back !== null) {
                this.back.next = null;
            } else {
                this.front = null;
            }
            this.size--;
            return value;
        }
    
        frontValue(): T | undefined {
            return this.front?.value;
        }
    
        backValue(): T | undefined {
            return this.back?.value;
        }
    
        getSize(): number {
            return this.size;
        }
    
        isEmpty(): boolean {
            return this.size === 0;
        }
    }
    
    

All Problems

All Solutions