Dada una array arr[] de N enteros distintos de cero, la tarea es encontrar la suma máxima de la array eliminando exactamente un conjunto contiguo de elementos positivos o negativos.
Ejemplos:
Entrada: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Salida: 4
Explicación: La suma máxima del arreglo se puede obtener eliminando el subarreglo arr[0, 1] desde arr [0, 1] tiene el mismo tipo de elementos, es decir, negativo. Por lo tanto, la suma requerida es 4.Entrada: arr[] = {2, -10, 4, 2, -8, -7}
Salida: -2
Explicación: La suma máxima del arreglo se puede obtener eliminando el subarreglo arr[4, 5] desde arr[4, 5] tiene el mismo tipo de elementos, es decir, negativo. Por lo tanto, la suma requerida es -2.
Enfoque: El problema dado se puede resolver en base a la siguiente observación, es decir, para obtener la suma máxima, se debe eliminar un conjunto contiguo de elementos negativos, ya que la eliminación de elementos positivos reducirá la suma de la array. Sin embargo, si no hay elementos negativos, elimine el elemento más pequeño de la array . Siga los pasos para resolver el problema:
- Recorre la array , arr[] y almacena la suma total de la array en la variable, digamos sum .
- Almacene la suma negativa contigua máxima en una variable, digamos max_neg .
- Si no hay elementos negativos en la array, actualice max_neg al elemento más pequeño de una array .
- Actualice el valor de sum a (sum – max_neg) .
- Imprime el valor de sum como resultado.
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 find the maximum sum of
// array after removing either the contiguous
// positive or negative elements
void maxSum(int arr[], int n)
{
// Store the total sum of array
int sum = 0;
// Store the maximum contiguous
// negative sum
int max_neg = INT_MAX;
// Store the sum of current
// contiguous negative elements
int tempsum = 0;
// Store the minimum element of array
int small = INT_MAX;
// Traverse the array, arr[]
for (int i = 0; i < n; i++) {
// Update the overall sum
sum += arr[i];
// Store minimum element of array
small = min(small, arr[i]);
// If arr[i] is positive
if (arr[i] > 0) {
// Update temp_sum to 0
tempsum = 0;
}
else {
// Add arr[i] to temp_sum
tempsum += arr[i];
}
// Update max_neg
max_neg = min(max_neg, tempsum);
}
// If no negative element in array
// then remove smallest positive element
if (max_neg == 0) {
max_neg = small;
}
// Print the required sum
cout << sum - max_neg;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxSum(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the maximum sum of
// array after removing either the contiguous
// positive or negative elements
static void maxSum(int arr[], int n)
{
// Store the total sum of array
int sum = 0;
// Store the maximum contiguous
// negative sum
int max_neg = Integer.MAX_VALUE;
// Store the sum of current
// contiguous negative elements
int tempsum = 0;
// Store the minimum element of array
int small = Integer.MAX_VALUE;
// Traverse the array, arr[]
for(int i = 0; i < n; i++)
{
// Update the overall sum
sum += arr[i];
// Store minimum element of array
small = Math.min(small, arr[i]);
// If arr[i] is positive
if (arr[i] > 0)
{
// Update temp_sum to 0
tempsum = 0;
}
else
{
// Add arr[i] to temp_sum
tempsum += arr[i];
}
// Update max_neg
max_neg = Math.min(max_neg, tempsum);
}
// If no negative element in array
// then remove smallest positive element
if (max_neg == 0)
{
max_neg = small;
}
// Print the required sum
System.out.println(sum - max_neg);
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = arr.length;
// Function Call
maxSum(arr, n);
}
}
// This code is contributed by Dharanendra L V.
Python3
# python 3 program for the above approach import sys # Function to find the maximum sum of # array after removing either the contiguous # positive or negative elements def maxSum(arr, n): # Store the total sum of array sum = 0 # Store the maximum contiguous # negative sum max_neg = sys.maxsize # Store the sum of current # contiguous negative elements tempsum = 0 # Store the minimum element of array small = sys.maxsize # Traverse the array, arr[] for i in range(n): # Update the overall sum sum += arr[i] # Store minimum element of array small = min(small, arr[i]) # If arr[i] is positive if (arr[i] > 0): # Update temp_sum to 0 tempsum = 0 else: # Add arr[i] to temp_sum tempsum += arr[i] # Update max_neg max_neg = min(max_neg, tempsum) # If no negative element in array # then remove smallest positive element if (max_neg == 0): max_neg = small # Print the required sum print(sum - max_neg) # Driver Code if __name__ == '__main__': # Given Input arr = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(arr) # Function Call maxSum(arr, n) # This code is contributed by bgangwar59.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum sum of
// array after removing either the contiguous
// positive or negative elements
function maxSum(arr, n) {
// Store the total sum of array
let sum = 0;
// Store the maximum contiguous
// negative sum
let max_neg = Number.MAX_SAFE_INTEGER;
// Store the sum of current
// contiguous negative elements
let tempsum = 0;
// Store the minimum element of array
let small = Number.MAX_SAFE_INTEGER;
// Traverse the array, arr[]
for (let i = 0; i < n; i++) {
// Update the overall sum
sum += arr[i];
// Store minimum element of array
small = Math.min(small, arr[i]);
// If arr[i] is positive
if (arr[i] > 0) {
// Update temp_sum to 0
tempsum = 0;
}
else {
// Add arr[i] to temp_sum
tempsum += arr[i];
}
// Update max_neg
max_neg = Math.min(max_neg, tempsum);
}
// If no negative element in array
// then remove smallest positive element
if (max_neg == 0) {
max_neg = small;
}
// Print the required sum
document.write(sum - max_neg);
}
// Driver Code
// Given Input
let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
let n = arr.length;
// Function Call
maxSum(arr, n);
// This code is contributed by gfgking.
</script>
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum sum of
// array after removing either the contiguous
// positive or negative elements
static void maxSum(int []arr, int n)
{
// Store the total sum of array
int sum = 0;
// Store the maximum contiguous
// negative sum
int max_neg = Int32.MaxValue;
// Store the sum of current
// contiguous negative elements
int tempsum = 0;
// Store the minimum element of array
int small = Int32.MaxValue;
// Traverse the array, arr[]
for(int i = 0; i < n; i++)
{
// Update the overall sum
sum += arr[i];
// Store minimum element of array
small = Math.Min(small, arr[i]);
// If arr[i] is positive
if (arr[i] > 0)
{
// Update temp_sum to 0
tempsum = 0;
}
else
{
// Add arr[i] to temp_sum
tempsum += arr[i];
}
// Update max_neg
max_neg = Math.Min(max_neg, tempsum);
}
// If no negative element in array
// then remove smallest positive element
if (max_neg == 0)
{
max_neg = small;
}
// Print the required sum
Console.Write(sum - max_neg);
}
// Driver Code
public static void Main(String[] args)
{
// Given Input
int []arr = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = arr.Length;
// Function Call
maxSum(arr, n);
}
}
// This code is contributed by shivanisinghss2110
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por adarsh_sinhg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA