Dada una array de enteros y dos valores k e i, donde k es el número de movimientos e i es el índice de la array. La tarea es recolectar el máximo de puntos en la array moviéndose en una o ambas direcciones desde el índice i dado y haciendo k movimientos. Tenga en cuenta que cada elemento de array visitado se considera un movimiento, incluido arr[i].
Restricciones:
n es el tamaño de la array.
0 <= yo < norte.
1 <= k <= norte
Ejemplos:
Input : arr[] = { 5, 6, 4, 2, 8, 3, 1 }
k = 3, i = 3
Output : Maximum point: 14
Explanation: arr[i] is 2
All possible ways to collect points in the array
by moving either both or a single direction are:
case 1: 6 + 4 + 2 = 12
case 2: 4 + 2 + 8 = 14
case 3: 2 + 8 + 3 = 13
So maximum points we collects in k moves : 14
Input : arr[] = { 5, 6, 4, 2, 8, 3, 1 }
k = 2, i = 5
Output : Maximum point: 11 ( 8 + 3 )
Una solución simple es generar todos los subarreglos de tamaño k (una cosa para notar que solo generamos subarreglos que contienen índice (I)), calcular sus sumas y finalmente devolver el máximo de todas las sumas. La complejidad temporal de esta solución es O(n*k)
Una solución eficiente se basa en el artículo sum_subarray máximo de tamaño k . La idea es utilizar el hecho de que la suma de un subarreglo de tamaño k se puede obtener usando la suma del subarreglo anterior de tamaño k. Excepto por el primer subarreglo de tamaño k, para otros subarreglos, calculamos la suma eliminando el primer elemento de la última ventana y agregando el último elemento de la ventana actual.
Complejidad temporal: O(n)
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to Collect maximum point
// in array with k moves.
#include <iostream>
using namespace std;
// function return maximum point
// that we can collect with K moves
int maximumPoints(int arr[], int n, int k, int i)
{
// Compute sum of first window of size k in which
// we consider subArray from index ( 'i-k' to 'i' )
// store starting index of sub_array
int start;
if (k > i)
// sub_array from ( 0 to I+(K-I))
start = 0;
else
// sub_array from ( i-i, to i )
start = i - k;
int res = 0;
for (int j = start; j <= start + k && j < n; j++)
res += arr[j];
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
int curr_sum = res;
for (int j = start + k + 1; j < n && j <= i + k; j++)
{
curr_sum += arr[j] - arr[j - k - 1];
res = max(res, curr_sum);
}
return res;
}
// Driver code
int main()
{
int arr[] = { 5, 6, 4, 2, 8, 3, 1 };
int k = 3, i = 3;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum points : "
<< maximumPoints(arr, n, k - 1, i);
return 0;
}
Java
// Java program to Collect maximum point
// in array with k moves.
class GFG {
// function return maximum point
// that we can collect with K moves
static int maximumPoints(int arr[], int n, int k, int i)
{
// Compute sum of first window of size k in which
// we consider subArray from index ( 'i-k' to 'i' )
// store starting index of sub_array
int start;
if (k > i)
// sub_array from ( 0 to I+(K-I))
start = 0;
else
// sub_array from ( i-i, to i )
start = i - k;
int res = 0;
for (int j = start; j <= start + k && j < n; j++)
res += arr[j];
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
int curr_sum = res;
for (int j = start + k + 1; j < n && j <= i + k; j++)
{
curr_sum += arr[j] - arr[j - k - 1];
res = Math.max(res, curr_sum);
}
return res;
}
// driver code
public static void main (String[] args)
{
int arr[] = { 5, 6, 4, 2, 8, 3, 1 };
int k = 3, i = 3;
int n = arr.length;
System.out.print("Maximum points : "
+maximumPoints(arr, n, k - 1, i));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to Collect maximum point
# in array with k moves.
# function return maximum point
# that we can collect with K moves
def maximumPoints(arr, n, k, i):
# Compute sum of first window of size k in which
# we consider subArray from index ( 'i-k' to 'i' )
# store starting index of sub_array
start = 0
if (k > i):
# sub_array from ( 0 to I+(K-I))
start = 0
else:
# sub_array from ( i-i, to i )
start = i - k
res = 0
j = start
while(j <= start + k and j < n):
res += arr[j]
j += 1
# Compute sums of remaining windows by
# removing first element of previous
# window and adding last element of
# current window.
curr_sum = res
j = start + k + 1
while(j < n and j <= i + k):
curr_sum += arr[j] - arr[j - k - 1]
res = max(res, curr_sum)
j += 1
return res
# Driver code
arr = [ 5, 6, 4, 2, 8, 3, 1 ]
k, i = 3, 3
n = len(arr)
print ("Maximum points :", maximumPoints(arr, n, k - 1, i))
# This code is contributed by Sachin Bisht
C#
// C# program to Collect maximum point
// in array with k moves.
using System;
class GFG {
// function return maximum point
// that we can collect with K moves
static int maximumPoints(int []arr, int n, int k, int i)
{
// Compute sum of first window of size k
// in which we consider subArray from
// index ( 'i-k' to 'i' ) and store
// starting index of sub_array
int start;
if (k > i)
// sub_array from ( 0 to I+(K-I))
start = 0;
else
// sub_array from ( i-i, to i )
start = i - k;
int res = 0;
for (int j = start; j <= start + k && j < n; j++)
res += arr[j];
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
int curr_sum = res;
for (int j = start + k + 1; j < n && j <= i + k; j++)
{
curr_sum += arr[j] - arr[j - k - 1];
res = Math.Max(res, curr_sum);
}
return res;
}
// driver code
public static void Main ()
{
int []arr = { 5, 6, 4, 2, 8, 3, 1 };
int k = 3, i = 3;
int n = arr.Length;
Console.Write("Maximum points : "
+maximumPoints(arr, n, k - 1, i));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to Collect maximum
// points in array with k moves.
// function return maximum po$
// that we can collect with K moves
function maximumPo($arr, $n, $k, $i)
{
// Compute sum of first
// window of size k in which
// we consider subArray from
// index ( 'i-k' to 'i' )
// store starting index of
// sub_array
$start;
if ($k > $i)
// sub_array from (0 to
// I + (K - I))
$start = 0;
else
// sub_array from (i - i, to i )
$start = $i - $k;
$res = 0;
for ($j = $start; $j <= $start +
$k and $j < $n; $j++)
$res += $arr[$j];
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
$curr_sum = $res;
for ($j = $start + $k + 1; $j < $n and
$j <= $i + $k; $j++)
{
$curr_sum += $arr[$j] - $arr[$j - $k - 1];
$res = max($res, $curr_sum);
}
return $res;
}
// Driver code
$arr = array(5, 6, 4, 2, 8, 3, 1);
$k = 3; $i = 3;
$n = count($arr);
echo "Maximum pos : ",
maximumPo($arr, $n, $k - 1, $i);
// This code is contributed by anuj_67
?>
Javascript
<script>
// Javascript program to Collect maximum point
// in array with k moves.
// function return maximum point
// that we can collect with K moves
function maximumPoints(arr, n, k, i)
{
// Compute sum of first window of size k in which
// we consider subArray from index ( 'i-k' to 'i' )
// store starting index of sub_array
var start;
if (k > i)
// sub_array from ( 0 to I+(K-I))
start = 0;
else
// sub_array from ( i-i, to i )
start = i - k;
var res = 0;
for (var j = start; j <= start + k && j < n; j++)
res += arr[j];
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window.
var curr_sum = res;
for (var j = start + k + 1; j < n && j <= i + k; j++)
{
curr_sum += arr[j] - arr[j - k - 1];
res = Math.max(res, curr_sum);
}
return res;
}
// Driver code
var arr = [ 5, 6, 4, 2, 8, 3, 1 ];
var k = 3, i = 3;
var n = arr.length;
document.write( "Maximum points : "
+ maximumPoints(arr, n, k - 1, i));
</script>
Maximum points : 14
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Nishant Singh . 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