Dada una array arr[] de enteros y un entero K , la tarea es encontrar la suma máxima tomando cada K -ésimo elemento, es decir, sum = arr[i] + arr[i + k] + arr[i + 2 * k] + arr[i + 3 * k] + ……. arr[i + q * k] comenzando con cualquier i .
Ejemplos:
Entrada: arr[] = {3, -5, 6, 3, 10}, K = 3
Salida: 10
Todas las secuencias posibles son:
3 + 3 = 6
-5 + 10 = 5
6 = 6
3 = 3
10 = 10
Entrada: arr[] = {3, 6, 4, 7, 2}, K = 2
Salida: 13
Enfoque ingenuo: la idea de resolver esto usando dos bucles anidados y encontrar la suma de cada secuencia a partir del índice i y sumar cada K -ésimo elemento hasta n , y encontrar el máximo de todos estos. La complejidad temporal de este método será O(N 2 )
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
int maxSum(int arr[], int n, int K)
{
// Initialize the maximum with
// the smallest value
int maximum = INT_MIN;
// Find maximum from all sequences
for (int i = 0; i < n; i++) {
int sumk = 0;
// Sum of the sequence
// starting from index i
for (int j = i; j < n; j += K)
sumk = sumk + arr[j];
// Update maximum
maximum = max(maximum, sumk);
}
return maximum;
}
// Driver code
int main()
{
int arr[] = { 3, 6, 4, 7, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << maxSum(arr, n, K);
return (0);
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
static int maxSum(int arr[], int n, int K)
{
// Initialize the maximum with
// the smallest value
int maximum = Integer.MIN_VALUE;
// Find maximum from all sequences
for (int i = 0; i < n; i++)
{
int sumk = 0;
// Sum of the sequence
// starting from index i
for (int j = i; j < n; j += K)
sumk = sumk + arr[j];
// Update maximum
maximum = Math.max(maximum, sumk);
}
return maximum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 6, 4, 7, 2 };
int n = arr.length;
int K = 2;
System.out.println(maxSum(arr, n, K));
}
}
// This code is contributed by Code_Mech
Python3
# Python 3 implementation of the approach import sys # Function to return the maximum sum for # every possible sequence such that # a[i] + a[i+k] + a[i+2k] + ... + a[i+qk] # is maximized def maxSum(arr, n, K): # Initialize the maximum with # the smallest value maximum = -sys.maxsize - 1 # Find maximum from all sequences for i in range(n): sumk = 0 # Sum of the sequence # starting from index i for j in range(i, n, K): sumk = sumk + arr[j] # Update maximum maximum = max(maximum, sumk) return maximum # Driver code if __name__ == '__main__': arr = [3, 6, 4, 7, 2] n = len(arr) K = 2 print(maxSum(arr, n, K)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
static int maxSum(int []arr, int n, int K)
{
// Initialize the maximum with
// the smallest value
int maximum = int.MinValue;
// Find maximum from all sequences
for (int i = 0; i < n; i++)
{
int sumk = 0;
// Sum of the sequence
// starting from index i
for (int j = i; j < n; j += K)
sumk = sumk + arr[j];
// Update maximum
maximum = Math.Max(maximum, sumk);
}
return maximum;
}
// Driver code
public static void Main()
{
int []arr = { 3, 6, 4, 7, 2 };
int n = arr.Length;
int K = 2;
Console.WriteLine(maxSum(arr, n, K));
}
}
// This code is contributed by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
function maxSum($arr, $n, $K)
{
// Initialize the maximum with
// the smallest value
$maximum = PHP_INT_MIN;
// Find maximum from all sequences
for ($i = 0; $i < $n; $i++)
{
$sumk = 0;
// Sum of the sequence
// starting from index i
for ($j = $i; $j < $n; $j += $K)
$sumk = $sumk + $arr[$j];
// Update maximum
$maximum = max($maximum, $sumk);
}
return $maximum;
}
// Driver code
$arr = array(3, 6, 4, 7, 2);
$n = sizeof($arr);
$K = 2;
echo maxSum($arr, $n, $K);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
function maxSum(arr, n, K)
{
// Initialize the maximum with
// the smallest value
var maximum = -1000000000;
// Find maximum from all sequences
for (var i = 0; i < n; i++) {
var sumk = 0;
// Sum of the sequence
// starting from index i
for (var j = i; j < n; j += K)
sumk = sumk + arr[j];
// Update maximum
maximum = Math.max(maximum, sumk);
}
return maximum;
}
// Driver code
var arr = [3, 6, 4, 7, 2];
var n = arr.length;
var K = 2;
document.write( maxSum(arr, n, K));
</script>
Producción:
13
Enfoque eficiente: este problema se puede resolver utilizando el concepto de arrays de sufijos , iteramos la array desde el lado derecho y almacenamos la suma de sufijos para cada elemento (i+k) (es decir, i+k < n) , y encontrar la suma máxima. La complejidad temporal de este método será O(N).
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
int maxSum(int arr[], int n, int K)
{
// Initialize the maximum with
// the smallest value
int maximum = INT_MIN;
// Initialize the sum array with zero
int sum[n] = { 0 };
// Iterate from the right
for (int i = n - 1; i >= 0; i--) {
// Update the sum starting at
// the current element
if (i + K < n)
sum[i] = sum[i + K] + arr[i];
else
sum[i] = arr[i];
// Update the maximum so far
maximum = max(maximum, sum[i]);
}
return maximum;
}
// Driver code
int main()
{
int arr[] = { 3, 6, 4, 7, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << maxSum(arr, n, K);
return (0);
}
Java
// Java implementation of the approach
class GFG {
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
static int maxSum(int arr[], int n, int K)
{
// Initialize the maximum with
// the smallest value
int maximum = Integer.MIN_VALUE;
// Initialize the sum array with zero
int[] sum = new int[n];
// Iterate from the right
for (int i = n - 1; i >= 0; i--) {
// Update the sum starting at
// the current element
if (i + K < n)
sum[i] = sum[i + K] + arr[i];
else
sum[i] = arr[i];
// Update the maximum so far
maximum = Math.max(maximum, sum[i]);
}
return maximum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 6, 4, 7, 2 };
int n = arr.length;
int K = 2;
System.out.print(maxSum(arr, n, K));
}
}
Python
# Python implementation of the approach # Function to return the maximum sum for # every possible sequence such that # a[i] + a[i + k] + a[i + 2k] + ... + a[i + qk] # is maximized def maxSum(arr, n, K): # Initialize the maximum with # the smallest value maximum = -2**32; # Initialize the sum array with zero sum = [0]*n # Iterate from the right for i in range(n-1, -1, -1): # Update the sum starting at # the current element if( i + K < n ): sum[i] = sum[i + K] + arr[i] else: sum[i] = arr[i]; # Update the maximum so far maximum = max( maximum, sum[i] ) return maximum; # Driver code arr = [3, 6, 4, 7, 2] n = len(arr); K = 2 print(maxSum(arr, n, K))
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
static int maxSum(int[] arr, int n, int K)
{
// Initialize the maximum with
// the smallest value
int maximum = int.MinValue;
// Initialize the sum array with zero
int[] sum = new int[n];
// Iterate from the right
for (int i = n - 1; i >= 0; i--) {
// Update the sum starting at
// the current element
if (i + K < n)
sum[i] = sum[i + K] + arr[i];
else
sum[i] = arr[i];
// Update the maximum so far
maximum = Math.Max(maximum, sum[i]);
}
return maximum;
}
// Driver code
public static void Main()
{
int[] arr = { 3, 6, 4, 7, 2 };
int n = arr.Length;
int K = 2;
Console.Write(maxSum(arr, n, K));
}
}
PHP
<?php
// PHP implementation of the approach
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
function maxSum($arr, $n, $K)
{
// Initialize the maximum with
// the smallest value
$maximum = PHP_INT_MIN;
// Initialize the sum array with zero
$sum = array($n);
// Iterate from the right
for ($i = $n - 1; $i >= 0; $i--)
{
// Update the sum starting at
// the current element
if ($i + $K < $n)
$sum[$i] = $sum[$i + $K] + $arr[$i];
else
$sum[$i] = $arr[$i];
// Update the maximum so far
$maximum = max($maximum, $sum[$i]);
}
return $maximum;
}
// Driver code
{
$arr = array(3, 6, 4, 7, 2 );
$n = sizeof($arr);
$K = 2;
echo(maxSum($arr, $n, $K));
}
// This code is contributed by Learner_
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the maximum sum for
// every possible sequence such that
// a[i] + a[i+k] + a[i+2k] + ... + a[i+qk]
// is maximized
function maxSum(arr, n, K)
{
// Initialize the maximum with
// the smallest value
var maximum = -1000000000;
// Initialize the sum array with zero
var sum = Array(n).fill(0);
// Iterate from the right
for (var i = n - 1; i >= 0; i--) {
// Update the sum starting at
// the current element
if (i + K < n)
sum[i] = sum[i + K] + arr[i];
else
sum[i] = arr[i];
// Update the maximum so far
maximum = Math.max(maximum, sum[i]);
}
return maximum;
}
// Driver code
var arr = [3, 6, 4, 7, 2 ];
var n = arr.length;
var K = 2;
document.write( maxSum(arr, n, K));
</script>
Producción:
13
Complejidad de tiempo: O(N) donde N es el número de elementos en la array.
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA