Encuentre la suma máxima de subsecuencias de acuerdo con las condiciones dadas

Dada una array de enteros nums y un entero K , la tarea es encontrar la suma máxima de una subsecuencia no vacía de la array tal que por cada dos enteros consecutivos en la subsecuencia, nums[i] y nums[j], donde i < j , se cumple la condición j – i <= K.
 

Una subsecuencia de una array se obtiene eliminando una cierta cantidad de elementos (puede ser cero) de la array, dejando los elementos restantes en su orden original. 
 

Ejemplos: 
 

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

Input: nums = [-1, -2, -3], K = 1
Output: -1

Input: nums = [10, -2, -10, -5, 20], K = 2
Output: 23

Acercarse: 

• La solución óptima de este problema se puede lograr utilizando la Programación Dinámica y Máxima de Ventana Deslizante .
• En cualquier índice i después de calcular la suma máxima para i, nums[i] ahora almacenará la suma máxima posible que se puede obtener de una subsecuencia que termina en i.
• Para calcular la suma máxima posible para cada índice i, verifique cuál es el valor máximo que se puede obtener de una ventana de tamaño K antes de él. Si el valor máximo es negativo, utilice cero en su lugar.
• Para usar los valores de las sumas calculadas de manera óptima, usamos un deque para almacenar las sumas junto con sus índices en un orden creciente de las sumas. También sacamos el elemento desde atrás cuando su índice sale de la ventana k del índice actual i.
   

// C++ program to find the maximum sum
// subsequence under given constraint
#include <bits/stdc++.h>
using namespace std;
 
// Function return the maximum sum
int ConstrainedSubsetSum(vector<int>& nums,
                         int k)
{
    deque<pair<int, int> > d;
     
    // Iterating the given array
    for (int i = 0; i < nums.size(); i++)
    {
        // Check if deque is empty
        nums[i] += d.size()
            ? max(d.back().first, 0) : 0;
         
        while (d.size() &&
               d.front().first < nums[i])
            d.pop_front();
         
        d.push_front({ nums[i], i });
         
        if (d.back().second == i - k)
            d.pop_back();
    }
 
    int ans = nums[0];
     
    for (auto x : nums)
        ans = max(ans, x);
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> nums = { 10, -2, -10,
                        -5, 20 };
    int K = 2;
     
    // Function call
    cout << ConstrainedSubsetSum(nums, K)
        << endl;
    return 0;
}

23

Complejidad de tiempo: O(N) 
Complejidad de espacio: O(K)