Subsecuencia de suma máxima con al menos k elementos distantes

Dado un arreglo y un número k, encuentre una subsecuencia tal que

  1. La suma de los elementos en la subsecuencia es máxima
  2. Los índices de los elementos de la subsecuencia difieren al menos en k

Ejemplos

Input : arr[] = {4, 5, 8, 7, 5, 4, 3, 4, 6, 5}
           k = 2
Output: 19
Explanation: The highest value is obtained 
if you pick indices 1, 4, 7, 10 giving 
4 + 7 + 3 + 5 = 19

Input: arr[] = {50, 70, 40, 50, 90, 70, 60, 
                              40, 70, 50}
           k = 2
Output: 230
Explanation: There are 10 elements and k = 2. 
If you select 2, 5, and 9 you get a total 
value of 230, which is the maximum possible.

Una solución simple es considerar todas las subsecuencias una por una. En cada subsecuencia, verifique la condición de distancia y devuelva la subsecuencia de suma máxima. Una solución eficiente es utilizar la programación dinámica

Hay dos casos:

  1. Si seleccionamos un elemento en el índice i tal que i + k + 1 >= N, entonces no podemos seleccionar ningún otro elemento como parte de la subsecuencia. Por lo tanto, debemos decidir si seleccionar este elemento o uno de los elementos posteriores.
  2. Si seleccionamos un elemento en el índice i tal que i + k + 1 < N, entonces el siguiente elemento que podemos seleccionar está en el índice i + k + 1. Por lo tanto, debemos decidir si seleccionar estos dos elementos o pasar al siguiente elemento adyacente.

Estos dos casos se pueden escribir como:

Let MS[i] denotes the maximum sum of subsequence 
from i = N-2 to 0. 

Base Case: 
   MS[N-1] = arr[N-1]

If  i + 1 + k >= N
   MS[i] = max(arr[i], MS[i+1]),  
Else
   MS[i] = max(arr[i] + MS[i+k+1], MS[i+1])

Evidently, the solution to the problem
is to find MS[0].

A continuación se muestra la implementación: 

C++

// CPP program to find maximum sum subsequence
// such that elements are at least k distance
// away.
#include <bits/stdc++.h>
using namespace std;
 
int maxSum(int arr[], int N, int k)
{
    // MS[i] is going to store maximum sum
    // subsequence in subarray from arr[i]
    // to arr[n-1]
    int MS[N];
 
    // We fill MS from right to left.
    MS[N - 1] = arr[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (i + k + 1 >= N)
            MS[i] = max(arr[i], MS[i + 1]);
        else
            MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
    }
 
    return MS[0];
}
 
// Driver code
int main()
{
    int N = 10, k = 2;
    int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
    cout << maxSum(arr, N, k);
    return 0;
}

Java

// Java program to find maximum sum subsequence
// such that elements are at least k distance
// away.
import java.io.*;
 
class GFG {
 
    static int maxSum(int arr[], int N, int k)
    {
        // MS[i] is going to store maximum sum
        // subsequence in subarray from arr[i]
        // to arr[n-1]
        int MS[] = new int[N];
 
        // We fill MS from right to left.
        MS[N - 1] = arr[N - 1];
        for (int i = N - 2; i >= 0; i--) {
            if (i + k + 1 >= N)
                MS[i] = Math.max(arr[i], MS[i + 1]);
            else
                MS[i] = Math.max(arr[i] + MS[i + k + 1],
                                MS[i + 1]);
        }
 
        return MS[0];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 10, k = 2;
        int arr[] = { 50, 70, 40, 50, 90, 70, 60,
                      40, 70, 50 };
        System.out.println(maxSum(arr, N, k));
    }
}
// This code is contributed by Prerna Saini

Python3

# Python3 program to find maximum
# sum subsequence such that elements
# are at least k distance away.
 
def maxSum(arr, N, k):
 
    # MS[i] is going to store maximum sum
    # subsequence in subarray from arr[i]
    # to arr[n-1]
    MS = [0 for i in range(N)]
 
    # We fill MS from right to left.
    MS[N - 1] = arr[N - 1]
    for i in range(N - 2, -1, -1):
        if (i + k + 1 >= N):
            MS[i] = max(arr[i], MS[i + 1])
        else:
            MS[i] = max(arr[i] + MS[i + k + 1],
                                 MS[i + 1])
     
    return MS[0]
 
# Driver code
N = 10; k = 2
arr = [ 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 ]
print(maxSum(arr, N, k))
     
# This code is contributed by Anant Agarwal.

C#

// C# program to find maximum sum
// subsequence such that elements
// are at least k distance away.
using System;
  
class GFG {
  
    static int maxSum(int []arr, int N, int k)
    {
        // MS[i] is going to store maximum sum
        // subsequence in subarray from arr[i]
        // to arr[n-1]
        int []MS = new int[N];
  
        // We fill MS from right to left.
        MS[N - 1] = arr[N - 1];
        for (int i = N - 2; i >= 0; i--) {
             
            if (i + k + 1 >= N)
                MS[i] = Math.Max(arr[i], MS[i + 1]);
            else
                MS[i] = Math.Max(arr[i] + MS[i + k + 1],
                                MS[i + 1]);
        }
  
        return MS[0];
    }
  
    // Driver code
    public static void Main()
    {
        int N = 10, k = 2;
        int []arr = { 50, 70, 40, 50, 90, 70, 60,
                                    40, 70, 50 };
        Console.WriteLine(maxSum(arr, N, k));
    }
}
 
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to find
// maximum sum subsequence
// such that elements are
// at least k distance
// away.
 
function maxSum($arr, $N, $k)
{
     
    // MS[i] is going to
    // store maximum sum
    // subsequence in
    // subarray from arr[i]
    // to arr[n-1]
 
    // We fill MS from
    // right to left.
    $MS[$N - 1] = $arr[$N - 1];
    for ($i = $N - 2; $i >= 0; $i--)
    {
        if ($i + $k + 1 >= $N)
            $MS[$i] = max($arr[$i],
                      $MS[$i + 1]);
        else
            $MS[$i] = max($arr[$i] +
                      $MS[$i + $k + 1],
                      $MS[$i + 1]);
    }
 
    return $MS[0];
}
 
// Driver code
$N = 10; $k = 2;
$arr = array(50, 70, 40, 50, 90,
             70, 60, 40, 70, 50);
echo(maxSum($arr, $N, $k));
 
// This code is contributed by Ajit.
?>
Producción

230

Complejidad del tiempo: O(n) Espacio auxiliar: O(n) Este artículo es una contribución de Sayan Mahapatra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *