2023-10-21 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 21

Description

Constrained Subsequence Sum

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

Solution

class Solution {
public:
  int constrainedSubsetSum(vector<int>& nums, int k) {
    deque<int> dq;
    for(int i = 0; i < nums.size(); ++i) {
      nums[i] += dq.size() ? nums[dq.front()] : 0;

      while(dq.size() && (i - dq.front() >= k || nums[i] >= nums[dq.back()])) {
        if(nums[i] >= nums[dq.back()]) {
          dq.pop_back();
        } else {
          dq.pop_front();
        }
      }

      if(nums[i] > 0) {
        dq.push_back(i);
      }
    }

    return *max_element(nums.begin(), nums.end());
  }
};

// Accepted
// 36/36 cases passed (240 ms)
// Your runtime beats 59.59 % of cpp submissions
// Your memory usage beats 98.57 % of cpp submissions (115 MB)
Algorithm