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. ?>
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