Dada una array A de n enteros y una array B de m enteros, encuentre la suma máxima de subarreglos contiguos de la array A tal que cualquier elemento de la array B no esté presente en ese subarreglo.
Ejemplos:
Entrada: A = {1, 7, -10, 6, 2}, B = {5, 6, 7, 1} Salida
: 2
Explicación Dado que el subarreglo de suma máxima de A no puede tener ningún elemento que esté presente en array B.
El subarreglo de suma máxima que satisface esto es {2} ya que los únicos subarreglos permitidos son: {-10} y {2}. El subarreglo de suma máxima es {2} que suma 2Entrada: A = {3, 4, 5, -4, 6}, B = {1, 8, 5} Salida
: 7
Explicación
El subarreglo de suma máxima que satisface esto es {3, 4} ya que los únicos subarreglos permitidos son {3 }, {4}, {3, 4}, {-4}, {6}, {-4, 6}. El subarreglo de suma máxima es {3, 4} que suma 7
Método 1 (enfoque O(n*m)):
Podemos resolver este problema usando el Algoritmo de Kadane . Dado que no queremos que ninguno de los elementos de la array B forme parte de ningún subarreglo de A, debemos modificar un poco el algoritmo clásico de Kadane.
Cada vez que consideramos un elemento en el algoritmo de Kadane, ampliamos el subarreglo actual o comenzamos un nuevo subarreglo.
curr_max = max(a[i], curr_max+a[i]); if (curr_max < 0) curr_max = 0
Ahora, en este problema, cuando consideramos cualquier elemento, verificamos buscando linealmente en la array B, si ese elemento está presente en B, entonces establecemos curr_max en cero, lo que significa que en ese índice todos los subarreglos que consideramos hasta ese punto terminarían y no se extenderá más ya que no se pueden formar más arrays contiguas, es decir
Si A i está presente en B, todos los subarreglos en A de 0 a (i – 1) no pueden extenderse más, ya que el i- ésimo elemento nunca puede incluirse en ningún subarreglo.
Si el elemento actual de la array A no forma parte de la array B, procedemos con el algoritmo de Kadane y realizamos un seguimiento de max_to_far.
C++
// C++ Program to find max subarray
// sum excluding some elements
#include <bits/stdc++.h>
using namespace std;
// Function to check the element
// present in array B
bool isPresent(int B[], int m, int x)
{
for (int i = 0; i < m; i++)
if (B[i] == x)
return true;
return false;
}
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
int findMaxSubarraySumUtil(int A[], int B[], int n, int m)
{
// set max_so_far to INT_MIN
int max_so_far = INT_MIN, curr_max = 0;
for (int i = 0; i < n; i++)
{
// if the element is present in B,
// set current max to 0 and move to
// the next element */
if (isPresent(B, m, A[i]))
{
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = max(A[i], curr_max + A[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
void findMaxSubarraySum(int A[], int B[], int n, int m)
{
int maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all elements
// of A are present in B, thus
// no subarray can be formed
if (maxSubarraySum == INT_MIN)
{
cout << "Maximum Subarray Sum cant be found"
<< endl;
}
else
{
cout << "The Maximum Subarray Sum = "
<< maxSubarraySum << endl;
}
}
// Driver Code
int main()
{
int A[] = { 3, 4, 5, -4, 6 };
int B[] = { 1, 8, 5 };
int n = sizeof(A) / sizeof(A[0]);
int m = sizeof(B) / sizeof(B[0]);
// Function call
findMaxSubarraySum(A, B, n, m);
return 0;
}
Java
// Java Program to find max subarray
// sum excluding some elements
import java.io.*;
class GFG {
// Function to check the element
// present in array B
static boolean isPresent(int B[], int m, int x)
{
for (int i = 0; i < m; i++)
if (B[i] == x)
return true;
return false;
}
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
static int findMaxSubarraySumUtil(int A[], int B[],
int n, int m)
{
// set max_so_far to INT_MIN
int max_so_far = -2147483648, curr_max = 0;
for (int i = 0; i < n; i++)
{
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (isPresent(B, m, A[i]))
{
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = Math.max(A[i], curr_max + A[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
static void findMaxSubarraySum(int A[], int B[], int n,
int m)
{
int maxSubarraySum
= findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all
// elements of A are present
// in B, thus no subarray can be formed
if (maxSubarraySum == -2147483648)
{
System.out.println("Maximum Subarray Sum"
+ " "
+ "can't be found");
}
else {
System.out.println("The Maximum Subarray Sum = "
+ maxSubarraySum);
}
}
// Driver code
public static void main(String[] args)
{
int A[] = { 3, 4, 5, -4, 6 };
int B[] = { 1, 8, 5 };
int n = A.length;
int m = B.length;
// Function call
findMaxSubarraySum(A, B, n, m);
}
}
// This code is contributed by Ajit.
Python3
# Python Program to find max
# subarray sum excluding some
# elements
# Function to check the element
# present in array B
INT_MIN = -2147483648
def isPresent(B, m, x):
for i in range(0, m):
if B[i] == x:
return True
return False
# Utility function for findMaxSubarraySum()
# with the following parameters
# A => Array A,
# B => Array B,
# n => Number of elements in Array A,
# m => Number of elements in Array B
def findMaxSubarraySumUtil(A, B, n, m):
# set max_so_far to INT_MIN
max_so_far = INT_MIN
curr_max = 0
for i in range(0, n):
if isPresent(B, m, A[i]) == True:
curr_max = 0
continue
# Proceed as in Kadane's Algorithm
curr_max = max(A[i], curr_max + A[i])
max_so_far = max(max_so_far, curr_max)
return max_so_far
# Wrapper for findMaxSubarraySumUtil()
def findMaxSubarraySum(A, B, n, m):
maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m)
# This case will occur when all
# elements of A are present
# in B, thus no subarray can be
# formed
if maxSubarraySum == INT_MIN:
print('Maximum Subarray Sum cant be found')
else:
print('The Maximum Subarray Sum =',
maxSubarraySum)
# Driver code
A = [3, 4, 5, -4, 6]
B = [1, 8, 5]
n = len(A)
m = len(B)
# Function call
findMaxSubarraySum(A, B, n, m)
# This code is contributed
# by sahil shelangia
C#
// C# Program to find max subarray
// sum excluding some elements
using System;
class GFG {
// Function to check the element
// present in array B
static bool isPresent(int[] B, int m, int x)
{
for (int i = 0; i < m; i++)
if (B[i] == x)
return true;
return false;
}
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
static int findMaxSubarraySumUtil(int[] A, int[] B,
int n, int m)
{
// set max_so_far to INT_MIN
int max_so_far = -2147483648, curr_max = 0;
for (int i = 0; i < n; i++)
{
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (isPresent(B, m, A[i]))
{
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = Math.Max(A[i], curr_max + A[i]);
max_so_far = Math.Max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
static void findMaxSubarraySum(int[] A, int[] B, int n,
int m)
{
int maxSubarraySum
= findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all
// elements of A are present
// in B, thus no subarray can be formed
if (maxSubarraySum == -2147483648)
{
Console.Write("Maximum Subarray Sum"
+ " "
+ "can't be found");
}
else {
Console.Write("The Maximum Subarray Sum = "
+ maxSubarraySum);
}
}
// Driver Code
static public void Main()
{
int[] A = { 3, 4, 5, -4, 6 };
int[] B = { 1, 8, 5 };
int n = A.Length;
int m = B.Length;
// Function call
findMaxSubarraySum(A, B, n, m);
}
}
// This code is contributed by Shrikant13.
PHP
<?php
// PHP Program to find max subarray
// sum excluding some elements
// Function to check the element
// present in array B
function isPresent($B, $m, $x)
{
for ($i = 0; $i < $m; $i++)
if ($B[$i] == $x)
return true;
return false;
}
// Utility function for
// findMaxSubarraySum()
// with the following
// parameters
// A => Array A,
// B => Array B,
// n => Number of elements
// in Array A,
// m => Number of elements
// in Array B
function findMaxSubarraySumUtil($A, $B,
$n, $m)
{
// set max_so_far
// to INT_MIN
$max_so_far = PHP_INT_MIN;
$curr_max = 0;
for ($i = 0; $i < $n; $i++)
{
// if the element is present
// in B, set current max to
// 0 and move to the next
// element
if (isPresent($B, $m, $A[$i]))
{
$curr_max = 0;
continue;
}
// Proceed as in
// Kadane's Algorithm
$curr_max = max($A[$i],
$curr_max + $A[$i]);
$max_so_far = max($max_so_far,
$curr_max);
}
return $max_so_far;
}
// Wrapper for
// findMaxSubarraySumUtil()
function findMaxSubarraySum($A, $B,
$n, $m)
{
$maxSubarraySum = findMaxSubarraySumUtil($A, $B,
$n, $m);
// This case will occur
// when all elements of
// A are present in
// B, thus no subarray
// can be formed
if ($maxSubarraySum == PHP_INT_MIN)
{
echo ("Maximum Subarray " .
"Sum cant be found\n");
}
else
{
echo ("The Maximum Subarray Sum = ".
$maxSubarraySum. "\n");
}
}
// Driver Code
$A = array(3, 4, 5, -4, 6);
$B = array(1, 8, 5);
$n = count($A);
$m = count($B);
// Function call
findMaxSubarraySum($A, $B, $n, $m);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript Program to find max subarray
// sum excluding some elements
// Function to check the element
// present in array B
function isPresent(B, m, x)
{
for (let i = 0; i < m; i++)
if (B[i] == x)
return true;
return false;
}
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
function findMaxSubarraySumUtil(A, B,n, m)
{
// set max_so_far to LET_MIN
let max_so_far = -2147483648, curr_max = 0;
for (let i = 0; i < n; i++)
{
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (isPresent(B, m, A[i]))
{
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = Math.max(A[i], curr_max + A[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
function findMaxSubarraySum(A, B, n,
m)
{
let maxSubarraySum
= findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all
// elements of A are present
// in B, thus no subarray can be formed
if (maxSubarraySum == -2147483648)
{
document.write("Maximum Subarray Sum"
+ " "
+ "can't be found");
}
else {
document.write("The Maximum Subarray Sum = "
+ maxSubarraySum);
}
}
// Driver code
let A = [ 3, 4, 5, -4, 6 ];
let B = [ 1, 8, 5 ];
let n = A.length;
let m = B.length;
// Function call
findMaxSubarraySum(A, B, n, m);
// This code is contributed by code_hunt.
</script>
Producción
The Maximum Subarray Sum = 7
Complejidad del tiempo: O(n*m)
Espacio Auxiliar: O(1)
Método 2 (enfoque O((n+m)*log(m)))
La idea principal detrás de este enfoque es exactamente la misma que la del método 1. Este enfoque solo hace que la búsqueda de un elemento de la array A, en la array B , más rápido usando la búsqueda binaria.
Nota: Necesitamos ordenar la array B para aplicarle la búsqueda binaria.
C++
// C++ Program to find max subarray
// sum excluding some elements
#include <bits/stdc++.h>
using namespace std;
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
int findMaxSubarraySumUtil(int A[], int B[], int n, int m)
{
// set max_so_far to INT_MIN
int max_so_far = INT_MIN, curr_max = 0;
for (int i = 0; i < n; i++) {
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (binary_search(B, B + m, A[i])) {
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = max(A[i], curr_max + A[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
void findMaxSubarraySum(int A[], int B[], int n, int m)
{
// sort array B to apply Binary Search
sort(B, B + m);
int maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all elements
// of A are present in B, thus no subarray
// can be formed
if (maxSubarraySum == INT_MIN) {
cout << "Maximum subarray sum cant be found"
<< endl;
}
else {
cout << "The Maximum subarray sum = "
<< maxSubarraySum << endl;
}
}
// Driver Code
int main()
{
int A[] = { 3, 4, 5, -4, 6 };
int B[] = { 1, 8, 5 };
int n = sizeof(A) / sizeof(A[0]);
int m = sizeof(B) / sizeof(B[0]);
// Function call
findMaxSubarraySum(A, B, n, m);
return 0;
}
Java
// Java Program to find max subarray
// sum excluding some elements
import java.util.*;
class GFG {
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
static int findMaxSubarraySumUtil(int A[], int B[],
int n, int m)
{
// set max_so_far to INT_MIN
int max_so_far = Integer.MIN_VALUE, curr_max = 0;
for (int i = 0; i < n; i++)
{
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (Arrays.binarySearch(B, A[i]) >= 0)
{
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = Math.max(A[i], curr_max + A[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
static void findMaxSubarraySum(int A[], int B[], int n,
int m)
{
// sort array B to apply Binary Search
Arrays.sort(B);
int maxSubarraySum
= findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all elements
// of A are present in B, thus no subarray
// can be formed
if (maxSubarraySum == Integer.MIN_VALUE)
{
System.out.println(
"Maximum subarray sum cant be found");
}
else
{
System.out.println("The Maximum subarray sum = "
+ maxSubarraySum);
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 3, 4, 5, -4, 6 };
int B[] = { 1, 8, 5 };
int n = A.length;
int m = B.length;
// Function call
findMaxSubarraySum(A, B, n, m);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python Program to find max subarray
# sum excluding some elements
# Utility function for findMaxSubarraySum()
# with the following parameters
# A => Array A,
# B => Array B,
# n => Number of elements in Array A,
# m => Number of elements in Array B
import sys
def binary_search(B, m, target):
start,end = 0,m - 1
# Iterate while start not meets end
while (start <= end):
# Find the mid index
mid = (start + end) // 2
# If element is present at mid, return True
if (B[mid] == target):
return True
# Else look in left or right half accordingly
elif (B[mid] < target):
start = mid + 1
else:
end = mid - 1
return False
def findMaxSubarraySumUtil(A, B, n, m):
# set max_so_far to INT_MIN
max_so_far,curr_max = -sys.maxsize - 1,0
for i in range(n):
# if the element is present in B,
# set current max to 0 and move to
# the next element
if (binary_search(B, m, A[i])):
curr_max = 0
continue
# Proceed as in Kadane's Algorithm
curr_max = max(A[i], curr_max + A[i])
max_so_far = max(max_so_far, curr_max)
return max_so_far
# Wrapper for findMaxSubarraySumUtil()
def findMaxSubarraySum(A,B,n,m):
# sort array B to apply Binary Search
B.sort()
maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m)
# This case will occur when all elements
# of A are present in B, thus no subarray
# can be formed
if (maxSubarraySum == -sys.maxsize - 1):
print("Maximum subarray sum cant be found")
else:
print(f"The Maximum subarray sum = {maxSubarraySum}")
# Driver Code
A = [ 3, 4, 5, -4, 6 ]
B = [ 1, 8, 5 ]
n = len(A)
m = len(B)
# Function call
findMaxSubarraySum(A, B, n, m)
# This code is contributed by shinjanpatra
C#
// C# Program to find max subarray
// sum excluding some elements
using System;
class GFG {
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
static int findMaxSubarraySumUtil(int []A, int []B,
int n, int m)
{
// set max_so_far to INT_MIN
int max_so_far = int.MinValue, curr_max = 0;
for (int i = 0; i < n; i++)
{
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (Array.BinarySearch(B, A[i]) >= 0)
{
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = Math.Max(A[i], curr_max + A[i]);
max_so_far = Math.Max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
static void findMaxSubarraySum(int []A, int []B, int n,
int m)
{
// sort array B to apply Binary Search
Array.Sort(B);
int maxSubarraySum
= findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all elements
// of A are present in B, thus no subarray
// can be formed
if (maxSubarraySum == int.MinValue)
{
Console.WriteLine(
"Maximum subarray sum cant be found");
}
else
{
Console.WriteLine("The Maximum subarray sum = "
+ maxSubarraySum);
}
}
// Driver Code
public static void Main(params string[] args)
{
int []A = { 3, 4, 5, -4, 6 };
int []B = { 1, 8, 5 };
int n = A.Length;
int m = B.Length;
// Function call
findMaxSubarraySum(A, B, n, m);
}
}
// This code is contributed by pratham76.
Javascript
<script>
// JavaScript Program to find max subarray
// sum excluding some elements
// Utility function for findMaxSubarraySum()
// with the following parameters
// A => Array A,
// B => Array B,
// n => Number of elements in Array A,
// m => Number of elements in Array B
function binary_search(B, m, target)
{
let start = 0, end = m - 1;
// Iterate while start not meets end
while (start <= end)
{
// Find the mid index
let mid = Math.floor((start + end)/2);
// If element is present at mid, return True
if (B[mid] === target) return true;
// Else look in left or right half accordingly
else if (B[mid] < target)
start = mid + 1;
else
end = mid - 1;
}
return false;
}
function findMaxSubarraySumUtil(A, B, n, m)
{
// set max_so_far to INT_MIN
let max_so_far = Number.MIN_VALUE, curr_max = 0;
for (let i = 0; i < n; i++) {
// if the element is present in B,
// set current max to 0 and move to
// the next element
if (binary_search(B, m, A[i])) {
curr_max = 0;
continue;
}
// Proceed as in Kadane's Algorithm
curr_max = Math.max(A[i], curr_max + A[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
return max_so_far;
}
// Wrapper for findMaxSubarraySumUtil()
function findMaxSubarraySum(A,B,n,m)
{
// sort array B to apply Binary Search
B.sort();
let maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m);
// This case will occur when all elements
// of A are present in B, thus no subarray
// can be formed
if (maxSubarraySum == Number.MIN_VALUE) {
document.write("Maximum subarray sum cant be found","</br>");
}
else {
document.write(`The Maximum subarray sum = ${maxSubarraySum}`,"</br>");
}
}
// Driver Code
let A = [ 3, 4, 5, -4, 6 ];
let B = [ 1, 8, 5 ];
let n = A.length;
let m = B.length;
// Function call
findMaxSubarraySum(A, B, n, m);
// This code is contributed by shinjanpatra
</script>
Producción
The Maximum subarray sum = 7
Complejidad de tiempo: O(nlog(m) + mlog(m)) o O((n + m)log(m)).
Nota: El factor mlog(m) se debe a la clasificación del arreglo B.
Espacio Auxiliar: O(1)
Método 3: enfoque O(max(n,m)))
La idea principal detrás de este enfoque es guardar la array B en un mapa que lo ayudará a verificar si A[i] está presente en B o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program implementation of the
// above idea
#include<bits/stdc++.h>
using namespace std;
// Function to calculate the max sum of contiguous
// subarray of B whose elements are not present in A
int findMaxSubarraySum(vector<int> A,vector<int> B)
{
unordered_map<int,int> m;
// mark all the elements present in B
for(int i=0;i<B.size();i++)
{
m[B[i]]=1;
}
// initialize max_so_far with INT_MIN
int max_so_far=INT_MIN;
int currmax=0;
// traverse the array A
for(int i=0;i<A.size();i++)
{
if(currmax<0 || m[A[i]]==1)
{
currmax=0;
continue;
}
currmax=max(A[i],A[i]+currmax);
// if current max is greater than
// max so far then update max so far
if(max_so_far<currmax)
{
max_so_far=currmax;
}
}
return max_so_far;
}
// Driver Code
int main()
{
vector<int> a = { 3, 4, 5, -4, 6 };
vector<int> b = { 1, 8, 5 };
// Function call
cout << findMaxSubarraySum(a,b);
return 0;
}
//This code is contributed by G.Vivek
Java
// Java Program implementation of the
// above idea
import java.util.*;
class GFG
{
// Function to calculate the max sum of contiguous
// subarray of B whose elements are not present in A
static int findMaxSubarraySum(int A[], int B[])
{
HashMap<Integer, Integer> m = new HashMap<>();
// mark all the elements present in B
for(int i = 0; i < B.length; i++)
{
m.put(B[i], 1);
}
// initialize max_so_far with INT_MIN
int max_so_far = Integer.MIN_VALUE;
int currmax = 0;
// traverse the array A
for(int i = 0; i < A.length; i++)
{
if(currmax < 0 || (m.containsKey(A[i]) && m.get(A[i]) == 1))
{
currmax = 0;
continue;
}
currmax = Math.max(A[i], A[i] + currmax);
// if current max is greater than
// max so far then update max so far
if(max_so_far < currmax)
{
max_so_far = currmax;
}
}
return max_so_far;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 3, 4, 5, -4, 6 };
int b[] = { 1, 8, 5 };
// Function call
System.out.println(findMaxSubarraySum(a, b));
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program implementation of the # above idea import sys # Function to calculate the max sum of # contiguous subarray of B whose elements # are not present in A def findMaxSubarraySum(A, B): m = dict() # Mark all the elements present in B for i in range(len(B)): if B[i] not in m: m[B[i]] = 0 m[B[i]] = 1 # Initialize max_so_far with INT_MIN max_so_far = -sys.maxsize - 1 currmax = 0 # Traverse the array A for i in range(len(A)): if (currmax < 0 or (A[i] in m and m[A[i]] == 1)): currmax = 0 continue currmax = max(A[i], A[i] + currmax) # If current max is greater than # max so far then update max so far if (max_so_far<currmax): max_so_far = currmax return max_so_far # Driver Code if __name__=='__main__': a = [ 3, 4, 5, -4, 6 ] b = [ 1, 8, 5 ] # Function call print(findMaxSubarraySum(a, b)) # This code is contributed by rutvik_56
C#
// C# Program implementation of the
// above idea
using System;
using System.Collections.Generic;
class GFG {
// Function to calculate the max sum of contiguous
// subarray of B whose elements are not present in A
static int findMaxSubarraySum(int[] A, int[] B)
{
Dictionary<int, int> m = new Dictionary<int, int>();
// mark all the elements present in B
for(int i = 0; i < B.Length; i++)
{
m[B[i]] = 1;
}
// initialize max_so_far with INT_MIN
int max_so_far = Int32.MinValue;
int currmax = 0;
// traverse the array A
for(int i = 0; i < A.Length; i++)
{
if(currmax<0 || (m.ContainsKey(A[i]) && m[A[i]] == 1))
{
currmax = 0;
continue;
}
currmax = Math.Max(A[i],A[i]+currmax);
// if current max is greater than
// max so far then update max so far
if(max_so_far<currmax)
{
max_so_far = currmax;
}
}
return max_so_far;
}
// Driver code.
static void Main() {
int[] a = { 3, 4, 5, -4, 6 };
int[] b = { 1, 8, 5 };
// Function call
Console.WriteLine(findMaxSubarraySum(a,b));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript program implementation of the
// above idea
// Function to calculate the max sum of
// contiguous subarray of B whose elements
// are not present in A
function findMaxSubarraySum(A, B){
let m = new Map()
// Mark all the elements present in B
for(let i=0;i<A.length;i++){
if(m.has(B[i]))
m.set(B[i],0)
m.set(B[i],1)
}
// Initialize max_so_far with INT_MIN
max_so_far = Number.MIN_VALUE
currmax = 0
// Traverse the array A
for(let i=0;i<A.length;i++){
if (currmax < 0 || (m.has(A[i]) && m.get(A[i]) == 1)){
currmax = 0
continue
}
currmax = Math.max(A[i], A[i] + currmax)
// If current max is greater than
// max so far then update max so far
if (max_so_far<currmax)
max_so_far = currmax
}
return max_so_far
}
// Driver Code
let a = [ 3, 4, 5, -4, 6 ]
let b = [ 1, 8, 5 ]
// Function call
document.write(findMaxSubarraySum(a, b),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
7
Complejidad del tiempo: O(max(n,m))
Espacio Auxiliar: O(n)