Suma máxima de subsecuencias tal que todos los elementos están separados por una distancia K

Dado un arreglo arr[] de N enteros y otro entero K . La tarea es encontrar la suma máxima de una subsecuencia tal que la diferencia de los índices de todos los elementos consecutivos en la subsecuencia en la array original sea exactamente K . Por ejemplo, si arr[i] es el primer elemento de la subsecuencia, entonces el siguiente elemento tiene que ser arr[i + k] , luego arr[i + 2k] y así sucesivamente.
Ejemplos: 
 

Entrada: arr[] = {2, -3, -1, -1, 2}, K = 2 
Salida: 3
Entrada: arr[] = {2, 3, -1, -1, 2}, K = 3 
Salida: 5 
 

Enfoque: Hay K secuencias posibles donde los elementos están separados por K distancias y estas pueden ser de las formas: 
 

0, 0 + k, 0 + 2k, …, 0 + n*k 
1, 1 + k, 1 + 2k, …, 1 + n*k 
2, 2 + k, 2 + 2k, …, 2 + n* k 
k-1, k-1 + k, k-1 + 2k, …, k-1 + n*k 
 

Ahora, cualquier subarreglo de las secuencias es una subsecuencia del arreglo original donde los elementos están a una distancia K entre sí.
Entonces, la tarea ahora se reduce a encontrar la suma máxima de subarreglo de estas secuencias que se puede encontrar mediante el algoritmo de Kadane .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the maximum subarray sum
// for the array {a[i], a[i + k], a[i + 2k], ...}
int maxSubArraySum(int a[], int n, int k, int i)
{
    int max_so_far = INT_MIN, max_ending_here = 0;
  
    while (i < n) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
  
        if (max_ending_here < 0)
            max_ending_here = 0;
  
        i += k;
    }
    return max_so_far;
}
  
// Function to return the sum of
// the maximum required subsequence
int find(int arr[], int n, int k)
{
    // To store the result
    int maxSum = 0;
  
    // Run a loop from 0 to k
    for (int i = 0; i <= min(n, k); i++) {
        int sum = 0;
  
        // Find the maximum subarray sum for the
        // array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = max(maxSum,
                     maxSubArraySum(arr, n, k, i));
    }
  
    // Return the maximum value
    return maxSum;
}
  
// Driver code
int main()
{
    int arr[] = { 2, -3, -1, -1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
  
    cout << find(arr, n, k);
  
    return 0;
}

// Java implementation of the approach 
import java.util.*;
  
class GFG
{
  
// Function to return the maximum subarray sum 
// for the array {a[i], a[i + k], a[i + 2k], ...} 
static int maxSubArraySum(int a[], int n, 
                          int k, int i) 
{ 
    int max_so_far = Integer.MIN_VALUE,
        max_ending_here = 0; 
  
    while (i < n) 
    { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 
  
        i += k; 
    } 
    return max_so_far; 
} 
  
// Function to return the sum of 
// the maximum required subsequence 
static int find(int arr[], int n, int k) 
{ 
    // To store the result 
    int maxSum = 0; 
  
    // Run a loop from 0 to k 
    for (int i = 0; i <= Math.min(n, k); i++)
    { 
        int sum = 0; 
  
        // Find the maximum subarray sum for the 
        // array {a[i], a[i + k], a[i + 2k], ...} 
        maxSum = Math.max(maxSum, 
                      maxSubArraySum(arr, n, k, i)); 
    } 
  
    // Return the maximum value 
    return maxSum; 
} 
  
// Driver code 
public static void main(String[] args) 
{
    int arr[] = {2, -3, -1, -1, 2};
    int n = arr.length;
    int k = 2;
  
    System.out.println(find(arr, n, k));
}
} 
  
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
# Function to return the maximum subarray sum
# for the array {a[i], a[i + k], a[i + 2k], ...}
import sys
def maxSubArraySum(a, n, k, i):
  
    max_so_far = -sys.maxsize;
    max_ending_here = 0;
  
    while (i < n):
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here;
  
        if (max_ending_here < 0):
            max_ending_here = 0;
  
        i += k;
      
    return max_so_far;
  
# Function to return the sum of
# the maximum required subsequence
def find(arr, n, k):
  
    # To store the result
    maxSum = 0;
  
    # Run a loop from 0 to k
    for i in range(0, min(n, k) + 1):
        sum = 0;
  
        # Find the maximum subarray sum for the
        # array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = max(maxSum,
                     maxSubArraySum(arr, n, k, i));
      
    # Return the maximum value
    return maxSum;
  
# Driver code
if __name__ == '__main__':
    arr = [ 2, -3, -1, -1, 2 ];
    n = len(arr);
    k = 2;
  
    print(find(arr, n, k));
  
# This code is contributed by Princi Singh

// C# implementation of the approach 
using System;
  
class GFG
{
      
    // Function to return the maximum subarray sum 
    // for the array {a[i], a[i + k], a[i + 2k], ...} 
    static int maxSubArraySum(int []a, int n, 
                              int k, int i) 
    { 
        int max_so_far = int.MinValue,
            max_ending_here = 0; 
      
        while (i < n) 
        { 
            max_ending_here = max_ending_here + a[i]; 
            if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 
      
            if (max_ending_here < 0) 
                max_ending_here = 0; 
      
            i += k; 
        } 
        return max_so_far; 
    } 
      
    // Function to return the sum of 
    // the maximum required subsequence 
    static int find(int []arr, int n, int k) 
    { 
        // To store the result 
        int maxSum = 0; 
      
        // Run a loop from 0 to k 
        for (int i = 0; i <= Math.Min(n, k); i++)
        { 
  
            // Find the maximum subarray sum for the 
            // array {a[i], a[i + k], a[i + 2k], ...} 
            maxSum = Math.Max(maxSum, 
                              maxSubArraySum(arr, n, k, i)); 
        } 
      
        // Return the maximum value 
        return maxSum; 
    } 
      
    // Driver code 
    public static void Main() 
    {
        int []arr = {2, -3, -1, -1, 2};
        int n = arr.Length;
        int k = 2;
      
        Console.WriteLine(find(arr, n, k));
    }    
}
  
// This code is contributed by AnkitRai01

<script>
  
// Javascript implementation of the approach
  
// Function to return the maximum subarray sum
// for the array {a[i], a[i + k], a[i + 2k], ...}
function maxSubArraySum(a, n, k, i)
{
    let max_so_far = Number.MIN_VALUE, 
        max_ending_here = 0;
  
    while (i < n) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
  
        if (max_ending_here < 0)
            max_ending_here = 0;
  
        i += k;
    }
    return max_so_far;
}
  
// Function to return the sum of
// the maximum required subsequence
function find(arr, n, k)
{
    // To store the result
    let maxSum = 0;
  
    // Run a loop from 0 to k
    for (let i = 0; i <= Math.min(n, k); i++) {
        let sum = 0;
  
        // Find the maximum subarray sum for the
        // array {a[i], a[i + k], a[i + 2k], ...}
        maxSum = Math.max(maxSum,
                     maxSubArraySum(arr, n, k, i));
    }
  
    // Return the maximum value
    return maxSum;
}
  
// Driver code
    let arr = [ 2, -3, -1, -1, 2 ];
    let n = arr.length;
    let k = 2;
  
    document.write(find(arr, n, k));
  
</script>

3

Complejidad temporal: O(min(n,k)*n)
Espacio auxiliar: O(1)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array