Dada una array arr[] que consta de N enteros y una array Q[][] , donde cada fila denota un rango {l, r} ( 0 ≤ l ≤ r ≤ N – 1 ). La tarea es encontrar la suma máxima de todos los subarreglos a partir del índice 0 reorganizando el arreglo excepto los elementos en los rangos dados en Q[][] .
Ejemplos:
Entrada: arr[] = {-8, 4, -2, -6, 4, 7, 1}, Q[][]= {{0, 0}, {4, 5}} Salida: -15
Explicación:
La array dada se puede reorganizar como {-8, 4, 1, -2, 4, 7, -6}. Ahora, la suma de todos los subarreglos a partir del primer índice son:
Suma de arr[0, 0] = -8
Suma de arr[0, 1] = -8 + 4 = -4
Suma de arr[0, 2] = -8 + 4 + 1 = -3
Suma de arr[0, 3] = -8 + 4 + 1 + (-2) = -5
Suma de arr[0, 4] = -8 + 4 +1 + ( -2) + 4 = -1
Suma de arr[0, 5] = -8 + 4 + 1 + (-2) + 4 + 7= 6
Suma de arr[0, 6] = -8 + 4 +1 + (-2) + 4 + 7 + (-6) = 0
La suma total = -8 + (-4) + (-3)+ (-5) + (-1) + 6 + 0 = -15Entrada: arr[] = {-8, 4, 3}, Q[][]= {{0, 2}}
Salida: -13
Explicación: Todos los elementos están presentes en el conjunto de rangos dado. Por lo tanto, ningún elemento puede reorganizarse. Ahora, la suma de todos los subarreglos del primer índice son:
Suma de arr[0, 0] = -8
Suma de arr[0, 1] = -8 + 4 = -4
Suma de arr[0, 2] = – 8 + 4 + 3 = -1
Suma total = -8 + (-4) + (-1) = -13
Enfoque: La idea es encontrar primero los elementos que no se pueden reorganizar. Luego, clasifique los elementos restantes en orden decreciente y asígnelos a los índices de modo que el elemento más grande se asigne al índice más pequeño que se permita reorganizar. Siga los pasos a continuación para resolver el problema:
- Cree un vector s y v para almacenar los índices y elementos respectivamente, que se pueden reorganizar.
- Recorra los elementos para cada rango {l, r} y márquelos como visitados.
- Recorra la array dada y almacene el índice i , si no está marcado como visitado.
- Ordena el vector v en orden descendente.
- Inserte el elemento en la array dada como arr[s[i]] = v[i] donde i corresponde al número de elementos que se pueden reorganizar.
- Después de los pasos anteriores, imprima la suma de las sumas de prefijos de la array dada como la suma máxima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the maximum sum
// all subarrays from the starting index
// after rearranging the array
int maxSum(int n, int a[], int l[][2], int q)
{
// Stores elements after rearranging
vector<int> v;
// Keeps track of visited elements
int d[n] = { 0 };
// Traverse the queries
for (int i = 0; i < q; i++) {
// Mark elements that are not
// allowed to rearranged
for (int x = l[i][0];
x <= l[i][1]; x++) {
if (d[x] == 0) {
d[x] = 1;
}
}
}
// Stores the indices
set<int> st;
// Get indices and elements that
// are allowed to rearranged
for (int i = 0; i < n; i++) {
// Store the current index and
// element
if (d[i] == 0) {
v.push_back(a[i]);
st.insert(i);
}
}
// Sort vector v in descending order
sort(v.begin(), v.end(),
greater<int>());
// Insert elements in array
int c = 0;
for (auto it : st) {
a[it] = v;
c++;
}
// Stores the resultant sum
int pref_sum = 0;
// Stores the prefix sums
int temp_sum = 0;
// Traverse the given array
for (int i = 0; i < n; i++) {
temp_sum += a[i];
pref_sum += temp_sum;
}
// Return the maximum sum
return pref_sum;
}
// Driver Code
int main()
{
// Given array
int arr[] = { -8, 4, -2, -6, 4, 7, 1 };
// Given size
int N = sizeof(arr) / sizeof(arr[0]);
// Queries
int q[][2] = { { 0, 0 }, { 4, 5 } };
// Number of queries
int queries = sizeof(q) / sizeof(q[0]);
// Function Call
cout << maxSum(N, arr, q, queries);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function that finds the maximum sum
// all subarrays from the starting index
// after rearranging the array
static int maxSum(int n, int a[], int [][]l, int q)
{
// Stores elements after rearranging
Vector<Integer> v = new Vector<>();
// Keeps track of visited elements
int []d = new int[n];
// Traverse the queries
for (int i = 0; i < q; i++)
{
// Mark elements that are not
// allowed to rearranged
for (int x = l[i][0];
x <= l[i][1]; x++)
{
if (d[x] == 0)
{
d[x] = 1;
}
}
}
// Stores the indices
HashSet<Integer> st = new HashSet<>();
// Get indices and elements that
// are allowed to rearranged
for (int i = 0; i < n; i++)
{
// Store the current index and
// element
if (d[i] == 0)
{
v.add(a[i]);
st.add(i);
}
}
// Sort vector v in descending order
Collections.sort(v);
Collections.reverse(v);
// Insert elements in array
int c = 0;
for (int it : st)
{
a[it] = v.get(c);
c++;
}
// Stores the resultant sum
int pref_sum = 0;
// Stores the prefix sums
int temp_sum = 0;
// Traverse the given array
for (int i = 0; i < n; i++)
{
temp_sum += a[i];
pref_sum += temp_sum;
}
// Return the maximum sum
return pref_sum;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int []arr = { -8, 4, -2, -6, 4, 7, 1 };
// Given size
int N = arr.length;
// Queries
int [][]q = { { 0, 0 }, { 4, 5 } };
// Number of queries
int queries = q.length;
// Function Call
System.out.print(maxSum(N, arr, q, queries));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the # above approach # Function that finds the # maximum sum all subarrays # from the starting index # after rearranging the array def maxSum(n, a, l, q): # Stores elements after # rearranging v = [] # Keeps track of visited # elements d = [0] * n # Traverse the queries for i in range(q): # Mark elements that are not # allowed to rearranged for x in range(l[i][0], l[i][1] + 1): if (d[x] == 0): d[x] = 1 # Stores the indices st = set([]) # Get indices and elements # that are allowed to rearranged for i in range(n): # Store the current index and # element if (d[i] == 0): v.append(a[i]) st.add(i) # Sort vector v in descending # order v.sort(reverse = True) # Insert elements in array c = 0 for it in st: a[it] = v c += 1 # Stores the resultant sum pref_sum = 0 # Stores the prefix sums temp_sum = 0 # Traverse the given array for i in range(n): temp_sum += a[i] pref_sum += temp_sum # Return the maximum sum return pref_sum # Driver Code if __name__ == "__main__": # Given array arr = [-8, 4, -2, -6, 4, 7, 1] # Given size N = len(arr) # Queries q = [[0, 0], [4, 5]] # Number of queries queries = len(q) # Function Call print(maxSum(N, arr, q, queries)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function that finds the maximum sum
// all subarrays from the starting index
// after rearranging the array
static int maxSum(int n, int []a, int [,]l, int q)
{
// Stores elements after rearranging
List<int> v = new List<int>();
// Keeps track of visited elements
int []d = new int[n];
// Traverse the queries
for (int i = 0; i < q; i++)
{
// Mark elements that are not
// allowed to rearranged
for (int x = l[i, 0];
x <= l[i, 1]; x++)
{
if (d[x] == 0)
{
d[x] = 1;
}
}
}
// Stores the indices
HashSet<int> st = new HashSet<int>();
// Get indices and elements that
// are allowed to rearranged
for (int i = 0; i < n; i++)
{
// Store the current index and
// element
if (d[i] == 0)
{
v.Add(a[i]);
st.Add(i);
}
}
// Sort vector v in descending order
v.Sort();
v.Reverse();
// Insert elements in array
int c = 0;
foreach (int it in st)
{
a[it] = v;
c++;
}
// Stores the resultant sum
int pref_sum = 0;
// Stores the prefix sums
int temp_sum = 0;
// Traverse the given array
for (int i = 0; i < n; i++)
{
temp_sum += a[i];
pref_sum += temp_sum;
}
// Return the maximum sum
return pref_sum;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { -8, 4, -2, -6, 4, 7, 1 };
// Given size
int N = arr.Length;
// Queries
int [,]q = { { 0, 0 }, { 4, 5 } };
// Number of queries
int queries = q.GetLength(0);
// Function Call
Console.Write(maxSum(N, arr, q, queries));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function that finds the maximum sum
// all subarrays from the starting index
// after rearranging the array
function maxSum(n, a, l, q)
{
// Stores elements after rearranging
let v = [];
// Keeps track of visited elements
let d = new Array(n);
for(let i = 0; i < n; i++)
{
d[i] = 0;
}
// Traverse the queries
for(let i = 0; i < q; i++)
{
// Mark elements that are not
// allowed to rearranged
for(let x = l[i][0];
x <= l[i][1]; x++)
{
if (d[x] == 0)
{
d[x] = 1;
}
}
}
// Stores the indices
let st = new Set();
// Get indices and elements that
// are allowed to rearranged
for(let i = 0; i < n; i++)
{
// Store the current index and
// element
if (d[i] == 0)
{
v.push(a[i]);
st.add(i);
}
}
// Sort vector v in descending order
v.sort(function(a, b){return b - a;});
// Insert elements in array
let c = 0;
for(let it of st.values())
{
a[it] = v;
c++;
}
// Stores the resultant sum
let pref_sum = 0;
// Stores the prefix sums
let temp_sum = 0;
// Traverse the given array
for(let i = 0; i < n; i++)
{
temp_sum += a[i];
pref_sum += temp_sum;
}
// Return the maximum sum
return pref_sum;
}
// Driver Code
// Given array
let arr = [ -8, 4, -2, -6, 4, 7, 1 ];
// Given size
let N = arr.length;
// Queries
let q = [ [ 0, 0 ], [ 4, 5 ] ];
// Number of queries
let queries = q.length;
// Function Call
document.write(maxSum(N, arr, q, queries));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
-15
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por amartyabhattacharya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA