Dada una array y un número k, encuentre la suma más grande de arrays contiguas en la array modificada que se forma al repetir la array dada k veces.
Ejemplos:
Input : arr[] = {-1, 10, 20}, k = 2
Output : 59
After concatenating array twice, we
get {-1, 10, 20, -1, 10, 20} which has
maximum subarray sum as 59.
Input : arr[] = {-1, -2, -3}, k = 3
Output : -1
Una solución simple es crear una array de tamaño n*k y luego ejecutar el algoritmo de Kadane . La complejidad del tiempo sería O(nk) y el espacio auxiliar sería O(n*k)
Una mejor solución es ejecutar un ciclo en la misma array y usar aritmética modular para retroceder comenzando después del final de la array.
C++
// C++ program to print largest contiguous
// array sum when array is created after
// concatenating a small array k times.
#include<bits/stdc++.h>
using namespace std;
// Returns sum of maximum sum subarray created
// after concatenating a[0..n-1] k times.
int maxSubArraySumRepeated(int a[], int n, int k)
{
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < n*k; i++)
{
// This is where it differs from Kadane's
// algorithm. We use modular arithmetic to
// find next element.
max_ending_here = max_ending_here + a[i%n];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {10, 20, -30, -1};
int n = sizeof(a)/sizeof(a[0]);
int k = 3;
cout << "Maximum contiguous sum is "
<< maxSubArraySumRepeated(a, n, k);
return 0;
}
Java
// Java program to print largest contiguous
// array sum when array is created after
// concatenating a small array k times.
import java.io.*;
class GFG {
// Returns sum of maximum sum
// subarray created after
// concatenating a[0..n-1] k times.
static int maxSubArraySumRepeated(int a[],
int n, int k)
{
int max_so_far = 0;
int INT_MIN, max_ending_here=0;
for (int i = 0; i < n*k; i++)
{
// This is where it differs from
// Kadane's algorithm. We use modular
// arithmetic to find next element.
max_ending_here = max_ending_here +
a[i % n];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Driver program to test maxSubArraySum
public static void main (String[] args) {
int a[] = {10, 20, -30, -1};
int n = a.length;
int k = 3;
System.out.println("Maximum contiguous sum is "
+ maxSubArraySumRepeated(a, n, k));
}
}
// This code is contributed by vt_m
Python3
# Python program to print
# largest contiguous
# array sum when array
# is created after
# concatenating a small
# array k times.
# Returns sum of maximum
# sum subarray created
# after concatenating
# a[0..n-1] k times.
def maxSubArraySumRepeated(a, n, k):
max_so_far = -2147483648
max_ending_here = 0
for i in range(n*k):
# This is where it
# differs from Kadane's
# algorithm. We use
# modular arithmetic to
# find next element.
max_ending_here = max_ending_here + a[i%n]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
if (max_ending_here < 0):
max_ending_here = 0
return max_so_far
# Driver program
# to test maxSubArraySum
a = [10, 20, -30, -1]
n = len(a)
k = 3
print("Maximum contiguous sum is ",
maxSubArraySumRepeated(a, n, k))
# This code is contributed
# by Anant Agarwal.
C#
// C# program to print largest contiguous
// array sum when array is created after
// concatenating a small array k times.
using System;
class GFG {
// Returns sum of maximum sum
// subarray created after
// concatenating a[0..n-1] k times.
static int maxSubArraySumRepeated(int []a,
int n,
int k)
{
int max_so_far = 0;
int max_ending_here=0;
for (int i = 0; i < n * k; i++)
{
// This is where it differs from
// Kadane's algorithm. We use modular
// arithmetic to find next element.
max_ending_here = max_ending_here +
a[i % n];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Driver Code
public static void Main ()
{
int []a = {10, 20, -30, -1};
int n = a.Length;
int k = 3;
Console.Write("Maximum contiguous sum is "
+ maxSubArraySumRepeated(a, n, k));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to print largest contiguous
// array sum when array is created after
// concatenating a small array k times.
// Returns sum of maximum
// sum subarray created
// after concatenating
// a[0..n-1] k times.
function maxSubArraySumRepeated($a, $n, $k)
{
$INT_MIN=0;
$max_so_far = $INT_MIN; $max_ending_here = 0;
for ($i = 0; $i < $n*$k; $i++)
{
// This is where it differs
// from Kadane's algorithm.
// We use modular arithmetic
// to find next element.
$max_ending_here = $max_ending_here +
$a[$i % $n];
if ($max_so_far < $max_ending_here)
$max_so_far = $max_ending_here;
if ($max_ending_here < 0)
$max_ending_here = 0;
}
return $max_so_far;
}
// Driver Code
$a = array(10, 20, -30, -1);
$n = sizeof($a);
$k = 3;
echo "Maximum contiguous sum is "
, maxSubArraySumRepeated($a, $n, $k);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to print largest contiguous
// array sum when array is created after
// concatenating a small array k times.
// Returns sum of maximum sum
// subarray created after
// concatenating a[0..n-1] k times.
function maxSubArraySumRepeated(a, n, k)
{
let max_so_far = 0;
let INT_MIN, max_ending_here=0;
for (let i = 0; i < n*k; i++)
{
// This is where it differs from
// Kadane's algorithm. We use modular
// arithmetic to find next element.
max_ending_here = max_ending_here +
a[i % n];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
// Driver code
let a = [10, 20, -30, -1];
let n = a.length;
let k = 3;
document.write("Maximum contiguous sum is "
+ maxSubArraySumRepeated(a, n, k));
// This code is contributed by sanjoy_62.
</script>
Producción :
Maximum contiguous sum is 30
Complejidad de tiempo : O(n*k)
Complejidad espacial : O(1)
¿Podemos usar la propiedad repetitiva de la array para obtener una mejor solución?