Dado un arreglo arr[] , la tarea es encontrar los índices inicial y final del subarreglo con la suma más grande después de excluir su elemento máximo.
Ejemplos:
Entrada: array[] = {5, -2, 10, -1, 4}
Salida: 1 5
Explicación:
Subarreglo[1:5] = {5, -2, 10, -1, 4}
Suma del subarreglo excluyendo el máximo elemento = 5 + (-2) + (-1) + 4 = 6
Entrada: arr[] = {5, 2, 5, 3, -30, -30, 6, 9}
Salida: 1 4
Explicación:
Subarreglo[ 1:4] = {5, 2, 5, 3}
Suma del subarreglo excluyendo el elemento máximo = 5 + 2 + 3 = 10
Enfoque: La idea es utilizar el algoritmo de Kadane para resolver este problema.
- Como en este problema, tenemos que elegir un elemento que sea el máximo en el subarreglo.
- Por lo tanto, podemos elegir todos los elementos positivos de la array, y cada vez podemos hacer elementos mayores que ese elemento a INT_MIN, de modo que no se incluya en la array.
- Finalmente, aplique el algoritmo de Kadane para encontrar el subarreglo de suma máxima .
- Si no hay elementos positivos en la array, podemos elegir cualquier elemento de la array para obtener la suma máxima como 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// maximum sum subarray such by
// excluding the maximum element
// from the subarray
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum
// subarray by excluding the maximum
// element from the array
void maximumSumSubarray(int arr[], int n)
{
unordered_map<int, int> mp;
// Loop to store all the positive
// elements in the map
for (int i = 0; i < n; i++) {
if (arr[i] >= 0
&& mp.find(arr[i])
== mp.end())
mp[arr[i]] = 1;
}
int first = 0;
int last = 0;
int ans = 0;
int INF = 1e6;
// Loop to iterating over the map
// and considering as the maximum
// element of the current including
// subarray
for (auto i : mp) {
// Make the current
// element maximum
int mx = i.first;
int curr = 0;
int curr_start;
// Iterate through array and
// apply kadane's algorithm
for (int j = 0; j < n; j++) {
if (curr == 0)
curr_start = j;
// Condition if current element is
// greater than mx then make
// the element -infinity
int val = arr[j] > mx
? -INF
: arr[j];
curr += val;
if (curr < 0)
curr = 0;
if (curr > ans) {
ans = curr;
// Store the indices
// in some variable
first = curr_start;
last = j;
}
}
}
cout << first + 1
<< " " << last + 1;
}
// Driver Code
int main()
{
int arr[] = { 5, -2, 10, -1, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
// Function Call
maximumSumSubarray(arr, size);
return 0;
}
Java
// Java implementation to find the
// maximum sum subarray such by
// excluding the maximum element
// from the subarray
import java.util.*;
class GFG{
// Function to find the maximum sum
// subarray by excluding the maximum
// element from the array
static void maximumSumSubarray(int arr[], int n)
{
Map<Integer, Integer> mp = new HashMap<>();
// Loop to store all the positive
// elements in the map
for(int i = 0; i < n; i++)
{
if (arr[i] >= 0)
mp.put(arr[i], 1);
}
int first = 0;
int last = 0;
int ans = 0;
int INF = (int)1e6;
// Loop to iterating over the map
// and considering as the maximum
// element of the current including
// subarray
for (Map.Entry<Integer,
Integer> i : mp.entrySet())
{
// Make the current
// element maximum
int mx = i.getKey();
int curr = 0;
int curr_start = -1;
// Iterate through array and
// apply kadane's algorithm
for(int j = 0; j < n; j++)
{
if (curr == 0)
curr_start = j;
// Condition if current element is
// greater than mx then make
// the element -infinity
int val = arr[j] > mx ? -INF : arr[j];
curr += val;
if (curr < 0)
curr = 0;
if (curr > ans)
{
ans = curr;
// Store the indices
// in some variable
first = curr_start;
last = j;
}
}
}
System.out.print((first + 1) + " " +
(last + 1));
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, -2, 10, -1, 4 };
int size = arr.length;
// Function call
maximumSumSubarray(arr, size);
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to find
# the maximum sum subarray such
# by excluding the maximum
# element from the subarray
# Function to find the maximum sum
# subarray by excluding the maximum
# element from the array
def maximumSumSubarray(arr, n):
mp = {}
# Loop to store all the positive
# elements in the map
for i in range(n):
if (arr[i] >= 0 and
arr[i] not in mp):
mp[arr[i]] = 1
first = 0
last = 0
ans = 0
INF = 1e6
# Loop to iterating over the map
# and considering as the maximum
# element of the current including
# subarray
for i in mp:
# Make the current
# element maximum
mx = i
curr = 0
# Iterate through array and
# apply kadane's algorithm
for j in range(n):
if (curr == 0):
curr_start = j
# Condition if current element
# is greater than mx then make
# the element -infinity
if arr[j] > mx:
val =- INF
else:
val= arr[j];
curr += val
if (curr < 0):
curr = 0
if (curr > ans):
ans = curr
# Store the indices
# in some variable
first = curr_start
last = j
print(first + 1, last + 1)
# Driver Code
if __name__ == "__main__":
arr = [ 5, -2, 10, -1, 4 ]
size = len(arr)
# Function Call
maximumSumSubarray(arr, size)
# This code is contributed by chitranayal
C#
// C# implementation to find the
// maximum sum subarray such by
// excluding the maximum element
// from the subarray
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum sum
// subarray by excluding the maximum
// element from the array
static void maximumSumSubarray(int []arr,
int n)
{
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Loop to store all the positive
// elements in the map
for(int i = 0; i < n; i++)
{
if (arr[i] >= 0)
mp.Add(arr[i], 1);
}
int first = 0;
int last = 0;
int ans = 0;
int INF = (int)1e6;
// Loop to iterating over the map
// and considering as the maximum
// element of the current including
// subarray
foreach (KeyValuePair<int,
int> i in mp)
{
// Make the current
// element maximum
int mx = i.Key;
int curr = 0;
int curr_start = -1;
// Iterate through array and
// apply kadane's algorithm
for(int j = 0; j < n; j++)
{
if (curr == 0)
curr_start = j;
// Condition if current element is
// greater than mx then make
// the element -infinity
int val = arr[j] > mx ?
-INF : arr[j];
curr += val;
if (curr < 0)
curr = 0;
if (curr > ans)
{
ans = curr;
// Store the indices
// in some variable
first = curr_start;
last = j;
}
}
}
Console.Write((first + 1) + " " +
(last + 1));
}
// Driver code
public static void Main(String[] args)
{
int []arr = {5, -2, 10, -1, 4};
int size = arr.Length;
// Function call
maximumSumSubarray(arr, size);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation to find the
// maximum sum subarray such by
// excluding the maximum element
// from the subarray
// Function to find the maximum sum
// subarray by excluding the maximum
// element from the array
function maximumSumSubarray(arr, n)
{
var mp = new Map();
// Loop to store all the positive
// elements in the map
for (var i = 0; i < n; i++) {
if (arr[i] >= 0
&& !mp.has(arr[i]))
mp.set(arr[i] , 1);
}
var first = 0;
var last = 0;
var ans = 0;
var INF = 1000000;
// Loop to iterating over the map
// and considering as the maximum
// element of the current including
// subarray
mp.forEach((value, key) => {
// Make the current
// element maximum
var mx = key;
var curr = 0;
var curr_start;
// Iterate through array and
// apply kadane's algorithm
for (var j = 0; j < n; j++) {
if (curr == 0)
curr_start = j;
// Condition if current element is
// greater than mx then make
// the element -infinity
var val = arr[j] > mx
? -INF
: arr[j];
curr += val;
if (curr < 0)
curr = 0;
if (curr > ans) {
ans = curr;
// Store the indices
// in some variable
first = curr_start;
last = j;
}
}
});
document.write( first + 1
+ " " + (last + 1));
}
// Driver Code
var arr = [5, -2, 10, -1, 4];
var size = arr.length;
// Function Call
maximumSumSubarray(arr, size);
</script>
Producción:
1 5
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA