Divida la array en tres subarreglos de modo que la suma del primer y el tercer subarreglo sea igual y máxima

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:
Divide los N números en [1, 3, 1], [] y [1, 4] 

Entrada: a[] = {1, 3, 2, 1, 4} 
Salida:
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:  

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)

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *