Dado un arreglo arr[] de longitud N , la tarea es encontrar el subarreglo contiguo de suma más grande agregando un entero S exactamente en K posiciones diferentes en el arreglo para cada K de [0, N] .
Ejemplos:
Entrada: arr[] = {4, 1, 3, 2}, S = 2
Salida: 10 12 14 16 18
Explicación:
Para k = 0, la suma del arreglo en sí es la suma máxima del subarreglo ya que no hay elemento negativo, por lo que 10.
Para k = 1, S se puede sumar en cualquier posición 1 para que la suma máxima del subarreglo sea 12.
Para k = 2, S se puede agregar en cualquier 2 posiciones para que la suma máxima del subarreglo sea 14.
Para k = 3, S se puede sumar en cualquiera de las 3 posiciones para que la suma máxima del subarreglo sea 16.
Para k = 4, S se puede agregar en cualquiera de las 4 posiciones para que la suma máxima del subarreglo sea 18.Entrada: arr[] = {-1, -3, 5, 10}, S = 2
Salida: 15 17 19 19 19
Enfoque: El enfoque se basa en la técnica de la suma de prefijos .
Inicialmente se calcula la suma del prefijo de la array y usando eso,
- La suma máxima de subarreglo de cada tamaño [1, N] se calcula y
- Luego, para cada valor de K, de [0, N], el valor de S se suma en K posiciones diferentes y
- La suma máxima se imprime como salida.
Siga estos pasos para resolver el problema anterior:
- Inicialice la array prefixsum[] para almacenar la suma de prefijos de la array y la array msum[] para almacenar la suma máxima de subarreglo de tamaño i.
- Ahora itere a través de la array y calcule la suma del prefijo de la array.
- Usando dos bucles for, calcule la suma máxima de subarreglo de cada tamaño i y guárdelo en msum[i].
- Ahora, para cada k de [0, n], agregue s en k posiciones distintas para maximizar la suma del subarreglo de tamaño i.
- Imprima la suma máxima de subarreglo para cada k.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for largest sum
// contiguous subarray by adding S
// exactly at K different positions
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest sum
// subarray after adding s at k
// different positions for k from [0, n]
void find_maxsum_subarray(
int arr[], int n, int s)
{
int msum[n];
int prefix_sum[n + 1] = { 0 };
prefix_sum[0] = 0;
// Find the prefix sum
for (int i = 0; i < n; i++) {
if (i == 0)
prefix_sum[i + 1] = arr[i];
else
prefix_sum[i + 1]
= arr[i]
+ prefix_sum[i];
}
// For each subarray of size i
// find the maximum sum
for (int i = 0; i < n; i++) {
int mx_sum = INT_MIN;
// Check for every subarray of size i
for (int j = 0; j < n - i; j++) {
mx_sum
= max(mx_sum,
prefix_sum[j + i + 1]
- prefix_sum[j]);
}
// Store the maximum sub array sum for
// each subarray of size i in msum array
msum[i] = mx_sum;
}
// For every k check the max sum
// subarray by adding s
// at k different positions
for (int k = 0; k <= n; k++) {
int mx_sum = 0;
// For each maxsum of subarray of size i
// check by s at k positions
// find the maximum sum
// after adding s at k positions
for (int i = 0; i < n; i++) {
mx_sum
= max(mx_sum,
msum[i]
+ min(i + 1, k) * s);
}
// For each k
// print the maximum subarray sum
cout << mx_sum << " ";
}
}
// Driver code
int main()
{
int arr[] = { 4, 1, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int s = 2;
find_maxsum_subarray(arr, n, s);
}
Java
// Java program for largest sum
// contiguous subarray by adding S
// exactly at K different positions
import java.io.*;
class GFG {
// Function to find the largest sum
// subarray after adding s at k
// different positions for k from [0, n]
static void find_maxsum_subarray(
int []arr, int n, int s)
{
int []msum = new int[n];
int []prefix_sum = new int[n + 1];
for(int i = 0; i < n + 1; i++) {
prefix_sum[i] = 0;
}
prefix_sum[0] = 0;
// Find the prefix sum
for (int i = 0; i < n; i++) {
if (i == 0)
prefix_sum[i + 1] = arr[i];
else
prefix_sum[i + 1]
= arr[i]
+ prefix_sum[i];
}
// For each subarray of size i
// find the maximum sum
for (int i = 0; i < n; i++) {
int mx_sum = Integer.MIN_VALUE;
// Check for every subarray of size i
for (int j = 0; j < n - i; j++) {
mx_sum
= Math.max(mx_sum,
prefix_sum[j + i + 1]
- prefix_sum[j]);
}
// Store the maximum sub array sum for
// each subarray of size i in msum array
msum[i] = mx_sum;
}
// For every k check the max sum
// subarray by adding s
// at k different positions
for (int k = 0; k <= n; k++) {
int mx_sum = 0;
// For each maxsum of subarray of size i
// check by s at k positions
// find the maximum sum
// after adding s at k positions
for (int i = 0; i < n; i++) {
mx_sum
= Math.max(mx_sum,
msum[i]
+ Math.min(i + 1, k) * s);
}
// For each k
// print the maximum subarray sum
System.out.print(mx_sum + " ");
}
}
// Driver code
public static void main (String[] args) {
int []arr = { 4, 1, 3, 2 };
int n = arr.length;
int s = 2;
find_maxsum_subarray(arr, n, s);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python3 program for largest sum # contiguous subarray by adding S # exactly at K different positions # Function to find the largest sum # subarray after adding s at k # different positions for k from [0, n] import sys def find_maxsum_subarray(arr, n, s): msum = [0]*n prefix_sum = [0]*(n+1) # Find the prefix sum for i in range(n): if (i == 0): prefix_sum[i + 1] = arr[i] else: prefix_sum[i + 1] = arr[i] + prefix_sum[i] # For each subarray of size i # find the maximum sum for i in range(n): mx_sum = -sys.maxsize-1 # Check for every subarray of size i for j in range(n - i): mx_sum = max(mx_sum,prefix_sum[j + i + 1]-prefix_sum[j]) # Store the maximum sub array sum for # each subarray of size i in msum array msum[i] = mx_sum # For every k check the max sum # subarray by adding s # at k different positions for k in range(n+1): mx_sum = 0 # For each maxsum of subarray of size i # check by s at k positions # find the maximum sum # after adding s at k positions for i in range(n): mx_sum = max(mx_sum,msum[i]+ min(i + 1, k) * s) # For each k # print the maximum subarray sum print(mx_sum,end=" ") # Driver code arr = [ 4, 1, 3, 2 ] n = len(arr) s = 2 find_maxsum_subarray(arr, n, s) # This code is contributed by shinjanpatra
C#
// C# program for largest sum
// contiguous subarray by adding S
// exactly at K different positions
using System;
class GFG
{
// Function to find the largest sum
// subarray after adding s at k
// different positions for k from [0, n]
static void find_maxsum_subarray(
int []arr, int n, int s)
{
int []msum = new int[n];
int []prefix_sum = new int[n + 1];
for(int i = 0; i < n + 1; i++) {
prefix_sum[i] = 0;
}
prefix_sum[0] = 0;
// Find the prefix sum
for (int i = 0; i < n; i++) {
if (i == 0)
prefix_sum[i + 1] = arr[i];
else
prefix_sum[i + 1]
= arr[i]
+ prefix_sum[i];
}
// For each subarray of size i
// find the maximum sum
for (int i = 0; i < n; i++) {
int mx_sum = Int32.MinValue;
// Check for every subarray of size i
for (int j = 0; j < n - i; j++) {
mx_sum
= Math.Max(mx_sum,
prefix_sum[j + i + 1]
- prefix_sum[j]);
}
// Store the maximum sub array sum for
// each subarray of size i in msum array
msum[i] = mx_sum;
}
// For every k check the max sum
// subarray by adding s
// at k different positions
for (int k = 0; k <= n; k++) {
int mx_sum = 0;
// For each maxsum of subarray of size i
// check by s at k positions
// find the maximum sum
// after adding s at k positions
for (int i = 0; i < n; i++) {
mx_sum
= Math.Max(mx_sum,
msum[i]
+ Math.Min(i + 1, k) * s);
}
// For each k
// print the maximum subarray sum
Console.Write(mx_sum + " ");
}
}
// Driver code
public static void Main()
{
int []arr = { 4, 1, 3, 2 };
int n = arr.Length;
int s = 2;
find_maxsum_subarray(arr, n, s);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for largest sum
// contiguous subarray by adding S
// exactly at K different positions
const INT_MIN = -2147483647 - 1;
// Function to find the largest sum
// subarray after adding s at k
// different positions for k from [0, n]
const find_maxsum_subarray = (arr, n, s) => {
let msum = new Array(n).fill(0);
let prefix_sum = new Array(n + 1).fill(0);
prefix_sum[0] = 0;
// Find the prefix sum
for (let i = 0; i < n; i++) {
if (i == 0)
prefix_sum[i + 1] = arr[i];
else
prefix_sum[i + 1]
= arr[i]
+ prefix_sum[i];
}
// For each subarray of size i
// find the maximum sum
for (let i = 0; i < n; i++) {
let mx_sum = INT_MIN;
// Check for every subarray of size i
for (let j = 0; j < n - i; j++) {
mx_sum
= Math.max(mx_sum,
prefix_sum[j + i + 1]
- prefix_sum[j]);
}
// Store the maximum sub array sum for
// each subarray of size i in msum array
msum[i] = mx_sum;
}
// For every k check the max sum
// subarray by adding s
// at k different positions
for (let k = 0; k <= n; k++) {
let mx_sum = 0;
// For each maxsum of subarray of size i
// check by s at k positions
// find the maximum sum
// after adding s at k positions
for (let i = 0; i < n; i++) {
mx_sum
= Math.max(mx_sum,
msum[i]
+ Math.min(i + 1, k) * s);
}
// For each k
// print the maximum subarray sum
document.write(`${mx_sum} `);
}
}
// Driver code
let arr = [4, 1, 3, 2];
let n = arr.length;
let s = 2;
find_maxsum_subarray(arr, n, s);
// This code is contributed by rakeshsahni
</script>
Producción
10 12 14 16 18
Complejidad de tiempo: O(N^2) donde N es el tamaño de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA