Dada una array arr[] de N enteros y un entero X , la tarea es encontrar la suma máxima posible de la subarray después de aplicar como máximo X intercambios.
Ejemplos:
Entrada: arr[] = {5, -1, 2, 3, 4, -2, 5}, X = 2
Salida: 19
Intercambiar (arr[0], arr[1]) y (arr[5], arr [6]).
Ahora, la suma máxima del subarreglo será (5 + 2 + 3 + 4 + 5) = 19
Entrada: arr[] = {-2, -3, -1, -10}, X = 10
Salida: -1
Enfoque: para cada subarreglo posible, considere los elementos que no forman parte de este subarreglo como descartados. Ahora, mientras quedan intercambios y la suma del subconjunto que se está considerando actualmente se puede maximizar, es decir, el elemento más grande entre los elementos descartados se puede intercambiar con el elemento mínimo del subconjunto, siga actualizando la suma de los subconjuntos. formación. Cuando no queden intercambios o la suma de la subarray no se pueda maximizar más, actualice la suma máxima actual de la subarray encontrada hasta el momento, que será la respuesta requerida al final.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum
// sub-array sum after at most x swaps
int SubarraySum(int a[], int n, int x)
{
// To store the required answer
int ans = -10000;
// For all possible intervals
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Keep current ans as zero
int curans = 0;
// To store the integers which are
// not part of the sub-array
// currently under consideration
priority_queue<int, vector<int> > pq;
// To store elements which are
// part of the sub-array
// currently under consideration
priority_queue<int, vector<int>, greater<int> > pq2;
// Create two sets
for (int k = 0; k < n; k++) {
if (k >= i && k <= j) {
curans += a[k];
pq2.push(a[k]);
}
else
pq.push(a[k]);
}
ans = max(ans, curans);
// Swap at most X elements
for (int k = 1; k <= x; k++) {
if (pq.empty() || pq2.empty()
|| pq2.top() >= pq.top())
break;
// Remove the minimum of
// the taken elements
curans -= pq2.top();
pq2.pop();
// Add maximum of the
// discarded elements
curans += pq.top();
pq.pop();
// Update the answer
ans = max(ans, curans);
}
}
}
// Return the maximized sub-array sum
return ans;
}
// Driver code
int main()
{
int a[] = { 5, -1, 2, 3, 4, -2, 5 }, x = 2;
int n = sizeof(a) / sizeof(a[0]);
cout << SubarraySum(a, n, x);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to return the maximum
// sub-array sum after at most x swaps
static int SubarraySum(int[] a, int n, int x)
{
// To store the required answer
int ans = -10000;
// For all possible intervals
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
// Keep current ans as zero
int curans = 0;
// To store the integers which are
// not part of the sub-array
// currently under consideration
ArrayList<Integer> pq = new ArrayList<Integer>();
// To store elements which are
// part of the sub-array
// currently under consideration
ArrayList<Integer> pq2 = new ArrayList<Integer>();
// Create two sets
for (int k = 0; k < n; k++) {
if (k >= i && k <= j) {
curans += a[k];
pq2.add(a[k]);
}
else
pq.add(a[k]);
}
Collections.sort(pq);
Collections.reverse(pq);
Collections.sort(pq2);
ans = Math.max(ans, curans);
// Swap at most X elements
for (int k = 1; k <= x; k++) {
if (pq.size() == 0 || pq2.size() == 0
|| pq2.get(0) >= pq.get(0))
break;
// Remove the minimum of
// the taken elements
curans -= pq2.get(0);
pq2.remove(0);
// Add maximum of the
// discarded elements
curans += pq.get(0);
pq.remove(0);
// Update the answer
ans = Math.max(ans, curans);
}
}
}
// Return the maximized sub-array sum
return ans;
}
// Driver code.
public static void main (String[] args)
{
int[] a = { 5, -1, 2, 3, 4, -2, 5 };
int x = 2;
int n = a.length;
System.out.println(SubarraySum(a, n, x));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the approach # Function to return the maximum # sub-array sum after at most x swaps def SubarraySum(a, n, x) : # To store the required answer ans = -10000 # For all possible intervals for i in range(n) : for j in range(i, n) : # Keep current ans as zero curans = 0 # To store the integers which are # not part of the sub-array # currently under consideration pq = [] # To store elements which are # part of the sub-array # currently under consideration pq2 = [] # Create two sets for k in range(n) : if (k >= i and k <= j) : curans += a[k] pq2.append(a[k]) else : pq.append(a[k]) pq.sort() pq.reverse() pq2.sort() ans = max(ans, curans) # Swap at most X elements for k in range(1, x + 1) : if (len(pq) == 0 or len(pq2) == 0 or pq2[0] >= pq[0]) : break # Remove the minimum of # the taken elements curans -= pq2[0] pq2.pop(0) # Add maximum of the # discarded elements curans += pq[0] pq.pop(0) # Update the answer ans = max(ans, curans) # Return the maximized sub-array sum return ans # Driver code a = [ 5, -1, 2, 3, 4, -2, 5 ] x = 2; n = len(a) print(SubarraySum(a, n, x)) # This ccode is contributed by divyesh072019.
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the maximum
// sub-array sum after at most x swaps
static int SubarraySum(int[] a, int n, int x)
{
// To store the required answer
int ans = -10000;
// For all possible intervals
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
// Keep current ans as zero
int curans = 0;
// To store the integers which are
// not part of the sub-array
// currently under consideration
List<int> pq = new List<int>();
// To store elements which are
// part of the sub-array
// currently under consideration
List<int> pq2 = new List<int>();
// Create two sets
for (int k = 0; k < n; k++) {
if (k >= i && k <= j) {
curans += a[k];
pq2.Add(a[k]);
}
else
pq.Add(a[k]);
}
pq.Sort();
pq.Reverse();
pq2.Sort();
ans = Math.Max(ans, curans);
// Swap at most X elements
for (int k = 1; k <= x; k++) {
if (pq.Count == 0 || pq2.Count == 0
|| pq2[0] >= pq[0])
break;
// Remove the minimum of
// the taken elements
curans -= pq2[0];
pq2.RemoveAt(0);
// Add maximum of the
// discarded elements
curans += pq[0];
pq.RemoveAt(0);
// Update the answer
ans = Math.Max(ans, curans);
}
}
}
// Return the maximized sub-array sum
return ans;
}
// Driver code.
static void Main() {
int[] a = { 5, -1, 2, 3, 4, -2, 5 };
int x = 2;
int n = a.Length;
Console.WriteLine(SubarraySum(a, n, x));
}
}
// This code is contributed by divyeshrabaiya07.
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximum
// sub-array sum after at most x swaps
function SubarraySum(a, n, x)
{
// To store the required answer
let ans = -10000;
// For all possible intervals
for (let i = 0; i < n; i++)
{
for (let j = i; j < n; j++)
{
// Keep current ans as zero
let curans = 0;
// To store the integers which are
// not part of the sub-array
// currently under consideration
let pq = [];
// To store elements which are
// part of the sub-array
// currently under consideration
let pq2 = [];
// Create two sets
for (let k = 0; k < n; k++) {
if (k >= i && k <= j) {
curans += a[k];
pq2.push(a[k]);
}
else
pq.push(a[k]);
}
pq.sort();
pq.reverse();
pq2.sort();
ans = Math.max(ans, curans);
// Swap at most X elements
for (let k = 1; k <= x; k++) {
if (pq.length == 0 || pq2.length == 0
|| pq2[0] >= pq[0])
break;
// Remove the minimum of
// the taken elements
curans -= pq2[0];
pq2.shift();
// Add maximum of the
// discarded elements
curans += pq[0];
pq.shift();
// Update the answer
ans = Math.max(ans, curans);
}
}
}
// Return the maximized sub-array sum
return ans;
}
let a = [ 5, -1, 2, 3, 4, -2, 5 ];
let x = 2;
let n = a.length;
document.write(SubarraySum(a, n, x));
// This code is contributed by suresh07.
</script>
Producción:
19
Complejidad de tiempo: O (n 3 logn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA