Dado un arreglo y un número k, encuentre una subsecuencia tal que
- La suma de los elementos en la subsecuencia es máxima
- 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:
- 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.
- 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