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

• Java
• C++
• Python
• Go

• 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
  }
  

All Problems

All Solutions