Dado un arreglo arr[] de N enteros positivos, la tarea es encontrar el subarreglo que tiene la suma máxima entre todos los subarreglos que tienen elementos únicos e imprimir su suma.
Input arr[] = {1, 2, 3, 3, 4, 5, 2, 1}
Output: 15
Explicación:
El subarreglo que tiene la suma máxima con elementos distintos es {3, 4, 5, 2, 1}.
Por lo tanto, la suma es = 3 + 4 + 5 + 2 + 1 = 15Entrada: array[] = {1, 2, 3, 1, 5}
Salida: 11
Explicación:
El subarreglo que tiene la suma máxima con elementos distintos es {2, 3, 1, 5}.
Por lo tanto, la suma es = 2 + 3 + 1 + 5 = 11.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y, para cada subarreglo, verificar si todos sus elementos son únicos o no. Encuentra la suma máxima entre dichos subarreglos e imprímelo.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente 1: Uso de la técnica de dos punteros
Para optimizar el enfoque anterior, la idea es utilizar la técnica Two Pointer . Siga los pasos a continuación para resolver el enfoque:
- Inicialice dos punteros i y j como 0 y 1 respectivamente para almacenar el índice inicial y final del subarreglo resultante.
- Inicialice un HashSet para almacenar los elementos de la array.
- Comience desde un subarreglo vacío con i = 0 y j = 0 y recorra el arreglo hasta que se encuentre cualquier elemento duplicado y actualice la suma actual a la suma máxima (digamos max_sum ) si se encuentra que es mayor que el max_sum actual .
- Si se encuentra el elemento duplicado, incremente j y actualice las variables hasta que solo queden elementos únicos en el subarreglo actual desde el índice j hasta i .
- Repita los pasos anteriores para el resto de la array y siga actualizando max_sum .
- Imprime la suma máxima obtenida después de completar los pasos anteriores.
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 to calculate required
// maximum subarray sum
int maxSumSubarray(int arr[], int n)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores the unique elements
set<int> set;
// Insert the first element
set.insert(arr[0]);
// Current max sum
int sum = arr[0];
// Global maximum sum
int maxsum = sum;
while (i < n - 1 && j < n)
{
// Update sum & increment j
// auto pos = s.find(3);
const bool is_in = set.find(arr[j]) !=
set.end();
if (!is_in)
{
sum = sum + arr[j];
maxsum = max(sum, maxsum);
// Add the current element
set.insert(arr[j++]);
}
// Update sum and increment i
// and remove arr[i] from set
else
{
sum -= arr[i];
// Remove the element
// from start position
set.erase(arr[i++]);
}
}
// Return the maximum sum
return maxsum;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = {1, 2, 3, 1, 5};
// Function Call
int ans = maxSumSubarray(arr, 5);
// Print the maximum sum
cout << (ans);
}
// This code is contributed by gauravrajput1
Java
// Java program for the above approach
import java.io.*;
import java.lang.Math;
import java.util.*;
public class GFG {
// Function to calculate required
// maximum subarray sum
public static int
maxSumSubarray(int[] arr)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores the unique elements
HashSet<Integer> set
= new HashSet<Integer>();
// Insert the first element
set.add(arr[0]);
// Current max sum
int sum = arr[0];
// Global maximum sum
int maxsum = sum;
while (i < arr.length - 1
&& j < arr.length) {
// Update sum & increment j
if (!set.contains(arr[j])) {
sum = sum + arr[j];
maxsum = Math.max(sum,
maxsum);
// Add the current element
set.add(arr[j++]);
}
// Update sum and increment i
// and remove arr[i] from set
else {
sum -= arr[i];
// Remove the element
// from start position
set.remove(arr[i++]);
}
}
// Return the maximum sum
return maxsum;
}
// Driver Code
public static void
main(String[] args)
{
// Given array arr[]
int arr[] = new int[] { 1, 2, 3, 1, 5 };
// Function Call
int ans = maxSumSubarray(arr);
// Print the maximum sum
System.out.println(ans);
}
}
Python3
# Python3 program for the above approach
# Function to calculate required
# maximum subarray sum
def maxSumSubarray(arr):
# Initialize two pointers
i = 0
j = 1
# Stores the unique elements
set = {}
# Insert the first element
set[arr[0]] = 1
# Current max sum
sum = arr[0]
# Global maximum sum
maxsum = sum
while (i < len(arr) - 1 and
j < len(arr)):
# Update sum & increment j
if arr[j] not in set:
sum = sum + arr[j]
maxsum = max(sum, maxsum)
# Add the current element
set[arr[j]] = 1
j += 1
# Update sum and increment i
# and remove arr[i] from set
else:
sum -= arr[i]
# Remove the element
# from start position
del set[arr[i]]
i += 1
# Return the maximum sum
return maxsum
# Driver Code
if __name__ == '__main__':
# Given array arr[]
arr = [ 1, 2, 3, 1, 5 ]
# Function call
ans = maxSumSubarray(arr)
# Print the maximum sum
print(ans)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate
// required maximum subarray sum
public static int maxSumSubarray(int[] arr)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores the unique elements
HashSet<int> set =
new HashSet<int>();
// Insert the first element
set.Add(arr[0]);
// Current max sum
int sum = arr[0];
// Global maximum sum
int maxsum = sum;
while (i < arr.Length - 1 &&
j < arr.Length)
{
// Update sum & increment j
if (!set.Contains(arr[j]))
{
sum = sum + arr[j];
maxsum = Math.Max(sum,
maxsum);
// Add the current element
set.Add(arr[j++]);
}
// Update sum and increment i
// and remove arr[i] from set
else
{
sum -= arr[i];
// Remove the element
// from start position
set.Remove(arr[i++]);
}
}
// Return the maximum sum
return maxsum;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = new int[] {1, 2,
3, 1, 5};
// Function Call
int ans = maxSumSubarray(arr);
// Print the maximum sum
Console.WriteLine(ans);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for
// the above approach
// Function to calculate required
// maximum subarray sum
function maxSumSubarray(arr, n)
{
// Initialize two pointers
var i = 0, j = 1;
// Stores the unique elements
var set = new Set();
// Insert the first element
set.add(arr[0]);
// Current max sum
var sum = arr[0];
// Global maximum sum
var maxsum = sum;
while (i < n - 1 && j < n)
{
// Update sum & increment j
// auto pos = s.find(3);
var is_in = set.has(arr[j]);
if (!is_in)
{
sum = sum + arr[j];
maxsum = Math.max(sum, maxsum);
// Add the current element
set.add(arr[j++]);
}
// Update sum and increment i
// and remove arr[i] from set
else
{
sum -= arr[i];
// Remove the element
// from start position
set.delete(arr[i++]);
}
}
// Return the maximum sum
return maxsum;
}
// Driver Code
// Given array arr[]
var arr = [ 1, 2, 3, 1, 5 ];
// Function Call
var ans = maxSumSubarray(arr, 5);
// Print the maximum sum
document.write(ans);
// This code is contributed by rutvik_56
</script>
Producción
11
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente 2: uso de la suma de prefijos
Para optimizar el enfoque anterior, la idea es utilizar la array Prefix Sum . Siga los pasos a continuación para resolver el enfoque:
- Cree una array que contenga la suma de todos los elementos antes del índice i. Esto se llama array de suma de prefijos.
- Cree un hashset que contenga el índice de la última aparición de un elemento.
- Inicialice la suma máxima global resultante con 0.
- Inicialice dos punteros i y j en el índice 0 y recorra la array con el puntero i.
- Si el elemento actual se ha producido antes, reinicialice j con el valor máximo entre j y la última aparición del elemento actual.
- La suma máxima global resultante = max(suma máxima global hasta ahora, prefixSum[i] – prefixSum[j] + elemento actual) como prefixSum[i] – prefixSum[j] nos dará la suma entre el índice i y j.
- Actualice la última aparición del elemento actual al índice i+1.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int maxSumUniqueSubarray(int* arr,int n)
{
// Create the prefix sum array
vector<int> preSum(n + 1);
preSum[0] = 0;
for (int i = 1; i <= n; i++)
preSum[i] = preSum[i - 1] + arr[i - 1];
// Create an hashset containing the index of last occurrence of an element
vector<int> lastSeen(1e4+1, 0);
// Initialize the resultant global maximum sum with 0.
int res = 0;
// Initialize two pointers i and j at index 0
// Traverse the array with the pointer i.
int j = 0;
for (int i = 0; i < n; i++)
{
int num = arr[i];
// If the current element has occurred before,
// reinitialize j with the maximum value between j and
// the last occurrence of the current element.
if (lastSeen[num] > 0)
{
j = max(j, lastSeen[num]);
}
// Update the resultant global maximum sum
res = max(res, preSum[i] + num - preSum[j]);
// Update the last occurrence of current element to index i+1.
lastSeen[num] = i + 1;
}
return res;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = {1, 2, 3, 1, 5};
// Function Call
int ans = maxSumUniqueSubarray(arr, 5);
// Print the maximum sum
cout << (ans);
}
// This code is contributed by akashkumarsen4
Producción
11
Complejidad de tiempo: O(N)
Espacio auxiliar: O(MAX(N,max_element))
Publicación traducida automáticamente
Artículo escrito por abhinaygupta98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA