Dada una array de enteros arr[] de tamaño N y dos enteros L y R . La tarea es encontrar el subarreglo de suma máxima de tamaño entre L y R (ambos inclusive).
Ejemplo:
Entrada: arr[] = {1, 2, 2, 1}, L = 1, R = 3
Salida: 5
Explicación:
El subarreglo de tamaño 1 son {1}, {2}, {2}, {1} y el máximo sum subarreglo = 2 para el subarreglo {2}.
El subarreglo de tamaño 2 es {1, 2}, {2, 2}, {2, 1}, y el subarreglo de suma máxima = 4 para el subarreglo {2, 2}.
El subarreglo de tamaño 3 es {1, 2, 2}, {2, 2, 1}, y el subarreglo de suma máxima = 5 para el subarreglo {2, 2, 1}.
Por lo tanto, el subarreglo de suma máxima posible es 5.
Entrada: arr[] = {-1, -3, -7, -11}, L = 1, R = 4
Salida: -1
Acercarse:
- Aquí usaremos el concepto de ventana deslizante que se discute en esta publicación.
- Primero calcule la suma del prefijo de la array en la array pre[] .
- A continuación, itere sobre el rango L a N -1 y considere todos los subarreglo de tamaño L a R .
- Cree un conjunto múltiple para almacenar sumas de prefijos de longitud de subarreglo L a R .
- Ahora, para encontrar el subarreglo de suma máxima que termina en el índice i , simplemente reste pre[i] y el mínimo de todos los valores de pre[i – L] a pre[i – R] .
- Finalmente devuelva el máximo de todas las sumas.
Aquí está la implementación del enfoque anterior:
C++
// C++ program to find Maximum sum
// subarray of size between L and R.
#include <bits/stdc++.h>
using namespace std;
// function to find Maximum sum subarray
// of size between L and R
void max_sum_subarray(vector<int> arr,
int L, int R)
{
int n = arr.size();
int pre[n] = { 0 };
// calculating prefix sum
pre[0] = arr[0];
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + arr[i];
}
multiset<int> s1;
// maintain 0 for initial
// values of i upto R
// Once i = R, then
// we need to erase that 0 from
// our multiset as our first
// index of subarray
// cannot be 0 anymore.
s1.insert(0);
int ans = INT_MIN;
ans = max(ans, pre[L - 1]);
// we maintain flag to
// counter if that initial
// 0 was erased from set or not.
int flag = 0;
for (int i = L; i < n; i++) {
// erase 0 from multiset once i=b
if (i - R >= 0) {
if (flag == 0) {
auto it = s1.find(0);
s1.erase(it);
flag = 1;
}
}
// insert pre[i-L]
if (i - L >= 0)
s1.insert(pre[i - L]);
// find minimum value in multiset.
ans = max(ans,
pre[i] - *s1.begin());
// erase pre[i-R]
if (i - R >= 0) {
auto it = s1.find(pre[i - R]);
s1.erase(it);
}
}
cout << ans << endl;
}
// Driver code
int main()
{
int L, R;
L = 1;
R = 3;
vector<int> arr = { 1, 2, 2, 1 };
max_sum_subarray(arr, L, R);
return 0;
}
Java
// Java program to find Maximum sum
// subarray of size between L and R.
import java.util.*;
class GFG {
// function to find Maximum sum subarray
// of size between L and R
static void max_sum_subarray(List<Integer> arr, int L, int R){
int n = arr.size();
int[] pre = new int[n + 1];
// calculating prefix sum
// here pre[0] = 0
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1]+arr.get(i - 1);
}
// treemap for storing prefix sums for
// subarray length L to R
TreeMap<Integer, Integer> s1 = new TreeMap<>();
int ans = Integer.MIN_VALUE;
for (int i = L; i <= n; i++) {
// if i > R, erase pre[i - R - 1]
// note that pre[0] = 0
if (i > R) {
// decrement count of pre[i - R - 1]
s1.put(pre[i - R - 1], s1.get(pre[i - R - 1])-1);
// if count is zero, element is not present
// in map so remove it
if (s1.get(pre[i - R - 1]) == 0)
s1.remove(pre[i - R - 1]);
}
// insert pre[i - L]
s1.put(pre[i - L], s1.getOrDefault(pre[i - L], 0)+1);
// find minimum value in treemap.
ans = Math.max(ans, pre[i] - s1.firstKey());
}
System.out.println(ans);
}
// Driver code
public static void main(String[] args){
int L, R;
L = 1;
R = 3;
List<Integer> arr = Arrays.asList(1, 2, 2, 1);
max_sum_subarray(arr, L, R);
}
}
// This code is contributed by Utkarsh Sharma
Python3
# Python3 program to find maximum sum # subarray of size between L and R. import sys # Function to find maximum sum subarray # of size between L and R def max_sum_subarray(arr, L, R): n = len(arr) pre = n * [0] # Calculating prefix sum pre[0] = arr[0] for i in range(1, n): pre[i] = pre[i - 1] + arr[i] s1 = [] # Maintain 0 for initial # values of i upto R # Once i = R, then # we need to erase that 0 from # our multiset as our first # index of subarray # cannot be 0 anymore. s1.append(0) ans = -sys.maxsize - 1 ans = max(ans, pre[L - 1]) # We maintain flag to # counter if that initial # 0 was erased from set or not. flag = 0 for i in range(L, n): # Erase 0 from multiset once i=b if (i - R >= 0): if (flag == 0): s1.remove(0) flag = 1 # Insert pre[i-L] if (i - L >= 0): s1.append(pre[i - L]) # Find minimum value in multiset. ans = max(ans, pre[i] - s1[0]) # Erase pre[i-R] if (i - R >= 0): s1.remove(pre[i - R]) print(ans) # Driver code if __name__ == "__main__": L = 1 R = 3 arr = [ 1, 2, 2, 1 ] max_sum_subarray(arr, L, R) # This code is contributed by chitranayal
C#
// C# program to find Maximum sum
// subarray of size between L and R.
using System;
using System.Collections.Generic;
class GFG
{
// function to find Maximum sum subarray
// of size between L and R
static void max_sum_subarray(List<int> arr, int L, int R)
{
int n = arr.Count;
int[] pre = new int[n];
// calculating prefix sum
pre[0] = arr[0];
for (int i = 1; i < n; i++)
{
pre[i] = pre[i - 1] + arr[i];
}
List<int> s1 = new List<int>();
// maintain 0 for initial
// values of i upto R
// Once i = R, then
// we need to erase that 0 from
// our multiset as our first
// index of subarray
// cannot be 0 anymore.
s1.Add(0);
int ans = Int32.MinValue;
ans = Math.Max(ans, pre[L - 1]);
// we maintain flag to
// counter if that initial
// 0 was erased from set or not.
int flag = 0;
for (int i = L; i < n; i++)
{
// erase 0 from multiset once i=b
if (i - R >= 0)
{
if (flag == 0)
{
int it = s1.IndexOf(0);
s1.RemoveAt(it);
flag = 1;
}
}
// insert pre[i-L]
if (i - L >= 0)
s1.Add(pre[i - L]);
// find minimum value in multiset.
ans = Math.Max(ans, pre[i] - s1[0]);
// erase pre[i-R]
if (i - R >= 0)
{
int it = s1.IndexOf(pre[i - R]);
s1.RemoveAt(it);
}
}
Console.WriteLine(ans);
}
// Driver code
static void Main()
{
int L, R;
L = 1;
R = 3;
List<int> arr = new List<int>(){1, 2, 2, 1};
max_sum_subarray(arr, L, R);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to find Maximum sum
// subarray of size between L and R.
// function to find Maximum sum subarray
// of size between L and R
function max_sum_subarray(arr,L,R)
{
let n = arr.length;
let pre = new Array(n);
// calculating prefix sum
pre[0] = arr[0];
for (let i = 1; i < n; i++)
{
pre[i] = pre[i - 1] + arr[i];
}
let s1 = []
// maintain 0 for initial
// values of i upto R
// Once i = R, then
// we need to erase that 0 from
// our multiset as our first
// index of subarray
// cannot be 0 anymore.
s1.push(0);
let ans = Number.MIN_VALUE;
ans = Math.max(ans, pre[L - 1]);
// we maintain flag to
// counter if that initial
// 0 was erased from set or not.
let flag = 0;
for (let i = L; i < n; i++)
{
// erase 0 from multiset once i=b
if (i - R >= 0)
{
if (flag == 0)
{
let it = s1.indexOf(0);
s1.splice(it,1);
flag = 1;
}
}
// insert pre[i-L]
if (i - L >= 0)
s1.push(pre[i - L]);
// find minimum value in multiset.
ans = Math.max(ans, pre[i] - s1[0]);
// erase pre[i-R]
if (i - R >= 0)
{
let it = s1.indexOf(pre[i - R]);
s1.splice(it,1);
}
}
document.write(ans);
}
// Driver code
let L, R;
L = 1;
R = 3;
let arr = [1, 2, 2, 1];
max_sum_subarray(arr, L, R);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5
Complejidad de Tiempo: O (N * log N)
Espacio Auxiliar: O (N)