Dado un arreglo de N enteros, la tarea es imprimir la suma del primer subarreglo dividiendo el arreglo en exactamente tres subarreglos de modo que la suma del primer y tercer elemento del subarreglo sean iguales y el máximo.
Nota: Todos los elementos deben pertenecer a un subarreglo y los subarreglos también pueden estar vacíos.
Ejemplos:
Entrada: a[] = {1, 3, 1, 1, 4}
Salida: 5
Divide los N números en [1, 3, 1], [] y [1, 4]Entrada: a[] = {1, 3, 2, 1, 4}
Salida: 4
Divide los N números en [1, 3], [2, 1] y [4]
MÉTODO 1
Un enfoque ingenuo es verificar todas las particiones posibles y usar el concepto de suma de prefijos para encontrar las particiones. La partición que dé la suma máxima del primer subarreglo será la respuesta.
Un enfoque eficiente es el siguiente:
- Almacene la suma de prefijos y la suma de sufijos de los N números.
- Hash el índice de la suma del sufijo usando un mapa_desordenado en C++ o mapa hash en Java.
- Iterar desde el comienzo de la array y verificar si la suma del prefijo existe en la array de sufijos más allá del índice actual i.
- Si es así, verifique el valor máximo anterior y actualice en consecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
#include <bits/stdc++.h>
using namespace std;
// Function to return the sum of
// the first subarray
int sumFirst(int a[], int n)
{
unordered_map<int, int> mp;
int suf = 0;
// calculate the suffix sum
for (int i = n - 1; i >= 0; i--)
{
suf += a[i];
mp[suf] = i;
}
int pre = 0;
int maxi = -1;
// iterate from beginning
for (int i = 0; i < n; i++)
{
// prefix sum
pre += a[i];
// check if it exists beyond i
if (mp[pre] > i)
{
// if greater then previous
// then update maximum
if (pre > maxi)
{
maxi = pre;
}
}
}
// First and second subarray empty
if (maxi == -1)
return 0;
// partition done
else
return maxi;
}
// Driver Code
int main()
{
int a[] = { 1, 3, 2, 1, 4 };
int n = sizeof(a) / sizeof(a[0]);
// Function call
cout << sumFirst(a, n);
return 0;
}
Java
// Java program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
import java.util.HashMap;
import java.util.Map;
class GfG {
// Function to return the sum
// of the first subarray
static int sumFirst(int a[], int n)
{
HashMap<Integer, Integer> mp = new HashMap<>();
int suf = 0;
// calculate the suffix sum
for (int i = n - 1; i >= 0; i--)
{
suf += a[i];
mp.put(suf, i);
}
int pre = 0, maxi = -1;
// iterate from beginning
for (int i = 0; i < n; i++)
{
// prefix sum
pre += a[i];
// check if it exists beyond i
if (mp.containsKey(pre) && mp.get(pre) > i)
{
// if greater then previous
// then update maximum
if (pre > maxi)
{
maxi = pre;
}
}
}
// First and second subarray empty
if (maxi == -1)
return 0;
// partition done
else
return maxi;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 3, 2, 1, 4 };
int n = a.length;
// Function call
System.out.println(sumFirst(a, n));
}
}
// This code is contributed by Rituraj Jain
Python3
# Python3 program for Split the array into three
# subarrays such that summation of first
# and third subarray is equal and maximum
# Function to return the sum of
# the first subarray
def sumFirst(a, n):
mp = {i: 0 for i in range(7)}
suf = 0
i = n - 1
# calculate the suffix sum
while(i >= 0):
suf += a[i]
mp[suf] = i
i -= 1
pre = 0
maxi = -1
# iterate from beginning
for i in range(n):
# prefix sum
pre += a[i]
# check if it exists beyond i
if (mp[pre] > i):
# if greater then previous
# then update maximum
if (pre > maxi):
maxi = pre
# First and second subarray empty
if (maxi == -1):
return 0
# partition done
else:
return maxi
# Driver Code
if __name__ == '__main__':
a = [1, 3, 2, 1, 4]
n = len(a)
# Function call
print(sumFirst(a, n))
# This code is contributed by
# Surendra_Gangwar
C#
// C# program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
using System;
using System.Collections.Generic;
class GfG {
// Function to return the sum
// of the first subarray
static int sumFirst(int[] a, int n)
{
Dictionary<int, int> mp
= new Dictionary<int, int>();
int suf = 0;
// calculate the suffix sum
for (int i = n - 1; i >= 0; i--)
{
suf += a[i];
mp.Add(suf, i);
if (mp.ContainsKey(suf))
{
mp.Remove(suf);
}
mp.Add(suf, i);
}
int pre = 0, maxi = -1;
// iterate from beginning
for (int i = 0; i < n; i++)
{
// prefix sum
pre += a[i];
// check if it exists beyond i
if (mp.ContainsKey(pre) && mp[pre] > i)
{
// if greater then previous
// then update maximum
if (pre > maxi)
{
maxi = pre;
}
}
}
// First and second subarray empty
if (maxi == -1)
return 0;
// partition done
else
return maxi;
}
// Driver code
public static void Main(String[] args)
{
int[] a = { 1, 3, 2, 1, 4 };
int n = a.Length;
// Function call
Console.WriteLine(sumFirst(a, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
// Function to return the sum of
// the first subarray
function sumFirst(a, n)
{
var mp = new Map();
var suf = 0;
// calculate the suffix sum
for (var i = n - 1; i >= 0; i--)
{
suf += a[i];
mp.set(suf, i);
}
var pre = 0;
var maxi = -1;
// iterate from beginning
for (var i = 0; i < n; i++)
{
// prefix sum
pre += a[i];
// check if it exists beyond i
if (mp.get(pre) > i)
{
// if greater then previous
// then update maximum
if (pre > maxi)
{
maxi = pre;
}
}
}
// First and second subarray empty
if (maxi == -1)
return 0;
// partition done
else
return maxi;
}
// Driver Code
var a = [1, 3, 2, 1, 4];
var n = a.length;
// Function call
document.write( sumFirst(a, n));
</script>
Producción
4
MÉTODO 2
Enfoque: Usaremos el concepto de dos punteros donde un puntero comenzará desde el frente y el otro desde atrás. En cada iteración se compara la suma del primer y último subarreglo y si son iguales se actualiza la suma en la variable respuesta.
Algoritmo:
- Inicialice front_pointer en 0 y back_pointer en n-1.
- Inicialice prefixsum en arr[ front_pointer ] y suffixsum en arr[back_pointer] .
- Se comparan las sumas.
– Si prefixsum > suffixsum , back_pointer se decrementa en 1 y suffixsum+= arr[ back_pointer ].
– Si prefixsum < suffixsum, front_pointer se incrementa en 1 y prefixsum+= arr[front_pointer]
– Si son iguales, la suma se actualiza en la variable de respuesta y ambos punteros se mueven un paso
y tanto prefixsum como suffixsum se actualizan en consecuencia . - El paso anterior se continúa hasta que el puntero_frontal no sea menor que el puntero_posterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
#include <bits/stdc++.h>
using namespace std;
// Function to return the sum of
// the first subarray
int sumFirst(int a[], int n)
{
// two pointers are initialized
// one at the front and the other
// at the back
int front_pointer = 0;
int back_pointer = n - 1;
// prefixsum and suffixsum initialized
int prefixsum = a[front_pointer];
int suffixsum = a[back_pointer];
// answer variable initialized to 0
int answer = 0;
while (front_pointer < back_pointer)
{
// if the summation are equal
if (prefixsum == suffixsum)
{
// answer updated
answer = max(answer, prefixsum);
// both the pointers are moved by step
front_pointer++;
back_pointer--;
// prefixsum and suffixsum are updated
prefixsum += a[front_pointer];
suffixsum += a[back_pointer];
}
else if (prefixsum > suffixsum)
{
// if prefixsum is more,then back pointer is
// moved by one step and suffixsum updated.
back_pointer--;
suffixsum += a[back_pointer];
}
else
{
// if prefixsum is less,then front pointer is
// moved by one step and prefixsum updated.
front_pointer++;
prefixsum += a[front_pointer];
}
}
// answer is returned
return answer;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 2, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << sumFirst(arr, n);
// This code is contributed by Arif
}
Java
// Java program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
import java.util.*;
class GFG{
// Function to return the sum of
// the first subarray
public static int sumFirst(int a[], int n)
{
// Two pointers are initialized
// one at the front and the other
// at the back
int front_pointer = 0;
int back_pointer = n - 1;
// prefixsum and suffixsum initialized
int prefixsum = a[front_pointer];
int suffixsum = a[back_pointer];
// answer variable initialized to 0
int answer = 0;
while (front_pointer < back_pointer)
{
// If the summation are equal
if (prefixsum == suffixsum)
{
// answer updated
answer = Math.max(answer, prefixsum);
// Both the pointers are moved by step
front_pointer++;
back_pointer--;
// prefixsum and suffixsum are updated
prefixsum += a[front_pointer];
suffixsum += a[back_pointer];
}
else if (prefixsum > suffixsum)
{
// If prefixsum is more,then back pointer is
// moved by one step and suffixsum updated.
back_pointer--;
suffixsum += a[back_pointer];
}
else
{
// If prefixsum is less,then front pointer is
// moved by one step and prefixsum updated.
front_pointer++;
prefixsum += a[front_pointer];
}
}
// answer is returned
return answer;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2, 1, 4 };
int n = arr.length;
// Function call
System.out.print(sumFirst(arr, n));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for Split the array into three # subarrays such that summation of first # and third subarray is equal and maximum import math # Function to return the sum of # the first subarray def sumFirst(a, n): # Two pointers are initialized # one at the front and the other # at the back front_pointer = 0 back_pointer = n - 1 # prefixsum and suffixsum initialized prefixsum = a[front_pointer] suffixsum = a[back_pointer] # answer variable initialized to 0 answer = 0 while (front_pointer < back_pointer): # If the summation are equal if (prefixsum == suffixsum): # answer updated answer = max(answer, prefixsum) # Both the pointers are moved by step front_pointer += 1 back_pointer -= 1 # prefixsum and suffixsum are updated prefixsum += a[front_pointer] suffixsum += a[back_pointer] elif (prefixsum > suffixsum): # If prefixsum is more,then back pointer is # moved by one step and suffixsum updated. back_pointer -= 1 suffixsum += a[back_pointer] else: # If prefixsum is less,then front pointer is # moved by one step and prefixsum updated. front_pointer += 1 prefixsum += a[front_pointer] # answer is returned return answer # Driver code arr = [ 1, 3, 2, 1, 4 ] n = len(arr) # Function call print(sumFirst(arr, n)) # This code is contributed by Stream_Cipher
C#
// C# program for split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
using System;
class GFG{
// Function to return the sum of
// the first subarray
static int sumFirst(int[] a, int n)
{
// Two pointers are initialized
// one at the front and the other
// at the back
int front_pointer = 0;
int back_pointer = n - 1;
// prefixsum and suffixsum initialized
int prefixsum = a[front_pointer];
int suffixsum = a[back_pointer];
// answer variable initialized to 0
int answer = 0;
while (front_pointer < back_pointer)
{
// If the summation are equal
if (prefixsum == suffixsum)
{
// answer updated
answer = Math.Max(answer, prefixsum);
// Both the pointers are moved by step
front_pointer++;
back_pointer--;
// prefixsum and suffixsum are updated
prefixsum += a[front_pointer];
suffixsum += a[back_pointer];
}
else if (prefixsum > suffixsum)
{
// If prefixsum is more,then back pointer is
// moved by one step and suffixsum updated.
back_pointer--;
suffixsum += a[back_pointer];
}
else
{
// If prefixsum is less,then front pointer is
// moved by one step and prefixsum updated.
front_pointer++;
prefixsum += a[front_pointer];
}
}
// answer is returned
return answer;
}
// Driver Code
static void Main()
{
int[] arr = { 1, 3, 2, 1, 4 };
int n = arr.Length;
// Function call
Console.WriteLine(sumFirst(arr, n));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// javascript program for Split the array into three
// subarrays such that summation of first
// and third subarray is equal and maximum
// Function to return the sum of
// the first subarray
function sumFirst(a, n)
{
// Two pointers are initialized
// one at the front and the other
// at the back
var front_pointer = 0;
var back_pointer = n - 1;
// prefixsum and suffixsum initialized
var prefixsum = a[front_pointer];
var suffixsum = a[back_pointer];
// answer variable initialized to 0
var answer = 0;
while (front_pointer < back_pointer)
{
// If the summation are equal
if (prefixsum == suffixsum)
{
// answer updated
answer = Math.max(answer, prefixsum);
// Both the pointers are moved by step
front_pointer++;
back_pointer--;
// prefixsum and suffixsum are updated
prefixsum += a[front_pointer];
suffixsum += a[back_pointer];
}
else if (prefixsum > suffixsum)
{
// If prefixsum is more,then back pointer is
// moved by one step and suffixsum updated.
back_pointer--;
suffixsum += a[back_pointer];
}
else
{
// If prefixsum is less,then front pointer is
// moved by one step and prefixsum updated.
front_pointer++;
prefixsum += a[front_pointer];
}
}
// answer is returned
return answer;
}
// Driver code
var arr = [ 1, 3, 2, 1, 4 ];
var n = arr.length;
// Function call
document.write(sumFirst(arr, n));
// This code is contributed by todaysgaurav
</script>
Producción
4
Complejidad temporal: O(n)
Espacio auxiliar: O(1)