Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma máxima de cualquier subarreglo posible después de eliminar como máximo un subarreglo de la array dada.
Ejemplos:
Entrada: arr[] = {-1, 5, 2, -1, 6}
Salida: 13
Explicación:
La suma máxima se puede obtener seleccionando el subarreglo {5, 2, -1, 6} y eliminando el subarreglo {- 1}.Entrada: arr[] = {7, 6, -1, -4, -5, 7, 1, -2, -3}
Salida: 21
Enfoque: Siga los pasos para resolver el problema:
- Encuentre el índice de la izquierda ( l ) y la derecha ( r ) número más + cinco en la array
- Si hay +ve números, calcule la suma del índice l a r
- de lo contrario, devuelva la suma máxima de la subarray (calcule usando el algoritmo de Kadane).
- Ahora, calcule la suma mínima del subarreglo (minSubArrSum) para el rango arr[lr] usando el algoritmo de Kadane
- Si minSubArrSum < 0 entonces el resultado = sum-minSubArrSum
- otro resultado = suma
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;
int kadaneMinSubArr(int* nums, int l, int r);
int kadaneMaxSubArr(int* nums, int l, int r);
void maxSubArrSum(int* nums, int n)
{
// !T(N) = O(n)
// !S(N) = O(1)
// finding the left most positive elements and right
// most positive elements indexes
int l = -1, r = -1, sum = 0, minSubSum;
// left most positive element
for (int i = 0; i < n; i++) {
if (nums[i] >= 0) {
l = i;
break;
}
}
// right most positive element
for (int i = n - 1; i >= 0; i--) {
if (nums[i] >= 0) {
r = i;
break;
}
}
if (l == -1 && r == -1) {
// all are -ve numbers
// maximum sum of subarray
cout << kadaneMaxSubArr(nums, 0, n - 1);
return;
}
// finding sum
for (int i = l; i <= r; i++)
sum += nums[i];
// minimum sum of subarray
minSubSum = kadaneMinSubArr(nums, l, r);
cout << ((minSubSum < 0) ? sum - minSubSum : sum);
}
int kadaneMaxSubArr(int* nums, int l, int r)
{
// l : left-bound index
// r : right-bound index
// !T(N) = O(N)
// !S(N) = O(1)
// finding the maxSubArrSum
int sum = nums[l], maxSum = nums[l];
for (int i = l; i <= r; i++) {
sum = max(sum + nums[i], nums[i]);
maxSum = max(maxSum, sum);
}
return maxSum;
}
int kadaneMinSubArr(int* nums, int l, int r)
{
// !T(N) = O(N)
// !S(N) = O(1)
// finding the minSubArrSum
int sum = nums[l], minSum = nums[l];
for (int i = l; i <= r; i++) {
sum = min(sum + nums[i], nums[i]);
minSum = min(minSum, sum);
}
return minSum;
}
// Driver Code
int main()
{
int arr[] = { 7, 6, -1, -4, -5, 7, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
maxSubArrSum(arr, n);
return 0;
}
// This code is contributed by jaladisishir96
C
// C program for the above approach
#include <stdio.h>
int kadaneMinSubArr(int* nums, int l, int r);
int kadaneMaxSubArr(int* nums, int l, int r);
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
void maxSubArrSum(int* nums, int n)
{
// !T(N) = O(n)
// !S(N) = O(1)
// finding the left most positive elements and right
// most positive elements indexes
int l = -1, r = -1, sum = 0, minSubSum;
// left most positive element
for (int i = 0; i < n; i++) {
if (nums[i] >= 0) {
l = i;
break;
}
}
// right most positive element
for (int i = n - 1; i >= 0; i--) {
if (nums[i] >= 0) {
r = i;
break;
}
}
if (l == -1 && r == -1) {
// all are -ve numbers
// maximum sum of subarray
printf("%d", kadaneMaxSubArr(nums, 0, n - 1));
return;
}
// finding sum
for (int i = l; i <= r; i++)
sum += nums[i];
// minimum sum of subarray
minSubSum = kadaneMinSubArr(nums, l, r);
(minSubSum < 0) ? printf("%d", sum - minSubSum)
: printf("%d", sum);
}
int kadaneMaxSubArr(int* nums, int l, int r)
{
// l : left-bound index
// r : right-bound index
// !T(N) = O(N)
// !S(N) = O(1)
// finding the maxSubArrSum
int sum = nums[l], maxSum = nums[l];
for (int i = l; i <= r; i++) {
sum = max(sum + nums[i], nums[i]);
maxSum = max(maxSum, sum);
}
return maxSum;
}
int kadaneMinSubArr(int* nums, int l, int r)
{
// !T(N) = O(N)
// !S(N) = O(1)
// finding the minSubArrSum
int sum = nums[l], minSum = nums[l];
for (int i = l; i <= r; i++) {
sum = min(sum + nums[i], nums[i]);
minSum = min(minSum, sum);
}
return minSum;
}
// Driver Code
int main()
{
int arr[] = { 7, 6, -1, -4, -5, 7, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
maxSubArrSum(arr, n);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find maximum
// subarray sum possible after
// removing at most one subarray
public static void maximumSum(
int arr[], int n)
{
long[] preSum = new long[n];
long sum = 0;
long maxSum = 0;
// Calculate the preSum[] array
for (int i = 0; i < n; i++) {
// Update the value of sum
sum = Math.max(arr[i],
sum + arr[i]);
// Update the value of maxSum
maxSum = Math.max(maxSum,
sum);
// Update the value of preSum[i]
preSum[i] = maxSum;
}
sum = 0;
maxSum = 0;
long[] postSum = new long[n + 1];
// Calculate the postSum[] array
for (int i = n - 1; i >= 0; i--) {
// Update the value of sum
sum = Math.max(arr[i],
sum + arr[i]);
// Update the value of maxSum
maxSum = Math.max(maxSum,
sum);
// Update the value of postSum[i]
postSum[i] = maxSum;
}
// Stores the resultant maximum
// sum of subarray
long ans = 0;
for (int i = 0; i < n; i++) {
// Update the value of ans
ans = Math.max(ans,
preSum[i]
+ postSum[i + 1]);
}
// Print the resultant sum
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 7, 6, -1, -4, -5, 7, 1 };
maximumSum(arr, arr.length);
}
}
Python3
# Python program for the above approach # Function to find maximum # subarray sum possible after # removing at most one subarray def maximumSum(arr, n) : preSum = [0] * n sum = 0 maxSum = 0 # Calculate the preSum[] array for i in range(n): # Update the value of sum sum = max(arr[i], sum + arr[i]) # Update the value of maxSum maxSum = max(maxSum, sum) # Update the value of preSum[i] preSum[i] = maxSum sum = 0 maxSum = 0 postSum = [0] * (n + 1) # Calculate the postSum[] array for i in range(n-1, -1, -1): # Update the value of sum sum = max(arr[i], sum + arr[i]) # Update the value of maxSum maxSum = max(maxSum, sum) # Update the value of postSum[i] postSum[i] = maxSum # Stores the resultant maximum # sum of subarray ans = 0 for i in range(n): # Update the value of ans ans = max(ans, preSum[i] + postSum[i + 1]) # Print resultant sum print(ans) # Driver code arr = [ 7, 6, -1, -4, -5, 7, 1] N = len(arr) maximumSum(arr, N) # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find maximum
// subarray sum possible after
// removing at most one subarray
public static void maximumSum(int[] arr, int n)
{
long[] preSum = new long[n];
long sum = 0;
long maxSum = 0;
// Calculate the preSum[] array
for(int i = 0; i < n; i++)
{
// Update the value of sum
sum = Math.Max(arr[i], sum + arr[i]);
// Update the value of maxSum
maxSum = Math.Max(maxSum, sum);
// Update the value of preSum[i]
preSum[i] = maxSum;
}
sum = 0;
maxSum = 0;
long[] postSum = new long[n + 1];
// Calculate the postSum[] array
for(int i = n - 1; i >= 0; i--)
{
// Update the value of sum
sum = Math.Max(arr[i], sum + arr[i]);
// Update the value of maxSum
maxSum = Math.Max(maxSum, sum);
// Update the value of postSum[i]
postSum[i] = maxSum;
}
// Stores the resultant maximum
// sum of subarray
long ans = 0;
for(int i = 0; i < n; i++)
{
// Update the value of ans
ans = Math.Max(ans, preSum[i] +
postSum[i + 1]);
}
// Print the resultant sum
Console.WriteLine(ans);
}
// Driver code
static void Main()
{
int[] arr = { 7, 6, -1, -4, -5, 7, 1 };
maximumSum(arr, arr.Length);
}
}
// This code is contributed by abhinavjain194
Javascript
<script>
// Javascript implementation of the above approach
// Function to find maximum
// subarray sum possible after
// removing at most one subarray
function maximumSum(
arr, n)
{
let preSum = Array.from({length: n}, (_, i) => 0);
let sum = 0;
let maxSum = 0;
// Calculate the preSum[] array
for (let i = 0; i < n; i++) {
// Update the value of sum
sum = Math.max(arr[i],
sum + arr[i]);
// Update the value of maxSum
maxSum = Math.max(maxSum,
sum);
// Update the value of preSum[i]
preSum[i] = maxSum;
}
sum = 0;
maxSum = 0;
let postSum = Array.from({length: n+1}, (_, i) => 0);
// Calculate the postSum[] array
for (let i = n - 1; i >= 0; i--) {
// Update the value of sum
sum = Math.max(arr[i],
sum + arr[i]);
// Update the value of maxSum
maxSum = Math.max(maxSum,
sum);
// Update the value of postSum[i]
postSum[i] = maxSum;
}
// Stores the resultant maximum
// sum of subarray
let ans = 0;
for (let i = 0; i < n; i++) {
// Update the value of ans
ans = Math.max(ans,
preSum[i]
+ postSum[i + 1]);
}
// Print the resultant sum
document.write(ans);
}
// Driver Code
let arr = [ 7, 6, -1, -4, -5, 7, 1 ];
maximumSum(arr, arr.length);
</script>
Producción:
21
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshitnsharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA