Dada una array de enteros arr de tamaño N . La tarea es encontrar el número máximo de divisiones tal que cada división tenga una suma divisible por 3 . No es necesario que todas las divisiones sean divisibles por 3 , la tarea es simplemente maximizar el número de divisiones que son divisibles por 3 .
Ejemplos:
Entrada: arr [] = [2, 36, 1, 9, 2, 0, 1, 8, 1]
Salida: 4
Explicación
La array se puede dividir en 4 partes:
[2, 36, 1] Suma = 39
[9 ] Suma = 9
[2, 0, 1] Suma = 3
[8, 1] Suma = 9
Todas las divisiones son divisibles por 3 y no puede haber más de 4 divisiones que sean divisibles por 3.
Entrada: arr [] = [40 , 40, 40, 5]
Salida: 1
Explicación:
la array se puede dividir en solo dos partes
[40, 40] Suma = 80.
[40, 5] Suma = 45.
La suma de la segunda división es divisible por 3, por lo tanto, solo una división es divisible por 3 por lo que la salida es 1.
Enfoque
Una observación que se puede hacer fácilmente es que es más fácil trabajar con la array si tomamos el módulo de cada elemento por 3. Porque no tendría ningún efecto en las divisiones. Ahora el problema se puede resolver usando Programación Dinámica .
- Sea dp[i] el número máximo de divisiones en la posición i .
- Luego calcule las sumas de prefijos módulo 3.
- Entonces, si un segmento tiene una suma divisible por 3 y su prefijo izquierdo y derecho, la suma también será la misma.
- Otra cosa a tener en cuenta es que las sumas de prefijos módulo 3 pueden ser 0, 1 o 2. Entonces, si el prefijo actual suma módulo 3 es 1. Elija el puntero izquierdo como el índice más a la derecha que tiene prefijo suma 1. O ignore el segmento y continúe.
dp[i] = max( dp[índice más a la derecha de 0 a i con suma de prefijo igual que i] + 1, dp[i-1])
dp[i-1] significa que no estamos considerando i como puntero derecho de algunos segmento
dp[el índice más a la derecha de 0 a i con el prefijo sum igual que i]+1 significa que i es un puntero derecho del segmento y el número total de divisiones será el número total de divisiones en el puntero izquierdo del segmento + 1 (para este segmento).
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 calculate_maximum_splits(int arr[], int N)
{
// Prefix array storing right most
// index with prefix sums 0, 1, 2
int pre[] = { 0, -1, -1 };
// dp array
int dp[N];
memset(dp, 0, sizeof(dp));
// Current prefix sum
int C = 0;
for(int i = 0; i < N; i++)
{
C = C + arr[i];
// Calculating the prefix sum modulo 3
C = C % 3;
// We dont have a left pointer
// with prefix sum C
if (pre[C] == -1)
{
dp[i] = dp[i - 1];
// We cannot consider i as
// a right pointer of any segment
}
else
{
// We have a left pointer
// pre[C] with prefix sum C
dp[i] = max(dp[i - 1], dp[pre[C]] + 1);
}
// i is the rightmost index of
// prefix sum C
pre[C] = i;
}
return dp[N - 1];
}
// Driver code
int main()
{
int arr[] = { 2, 36, 1, 9, 2, 0, 1, 8, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << (calculate_maximum_splits(arr, N));
}
// This code is contributed by chitranayal
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
static int calculate_maximum_splits(int arr[],
int N)
{
// Prefix array storing right most
// index with prefix sums 0, 1, 2
int pre[] = { 0, -1, -1 };
// dp array
int[] dp = new int[N];
Arrays.fill(dp, 0);
// Current prefix sum
int C = 0;
for(int i = 0; i < N; i++)
{
C = C + arr[i];
// Calculating the prefix sum modulo 3
C = C % 3;
// We dont have a left pointer
// with prefix sum C
if (pre[C] == -1)
{
if(1 <= i)
dp[i] = dp[i - 1];
// We cannot consider i as
// a right pointer of any segment
}
else
{
// We have a left pointer
// pre[C] with prefix sum C
dp[i] = Math.max(dp[i - 1],
dp[pre[C]] + 1);
}
// i is the rightmost index of
// prefix sum C
pre[C] = i;
}
return dp[N - 1];
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 36, 1, 9, 2, 0, 1, 8, 1 };
int N = arr.length;
System.out.println(calculate_maximum_splits(arr, N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for above approach def calculate_maximum_splits(arr, N): # prefix array storing right most # index with prefix sums 0, 1, 2 pre =[0, -1, -1] # dp array dp =[0 for i in range(N)] # current prefix sum C = 0 for i in range(N): C = C + arr[i] # Calculating the prefix sum modulo 3 C = C % 3 # We dont have a left pointer # with prefix sum C if pre[C]==-1: dp[i]= dp[i-1] # We cannot consider i as # a right pointer of any segment else: # We have a left pointer # pre[C] with prefix sum C dp[i]= max(dp[i-1], dp[pre[C]]+1) # i is the rightmost index of # prefix sum C pre[C]= i return dp[N-1] # Driver code arr = [2, 36, 1, 9, 2, 0, 1, 8, 1] N = len(arr) print(calculate_maximum_splits(arr, N))
C#
// C# implementation of the above approach
using System;
class GFG{
static int calculate_maximum_splits(int []arr,
int N)
{
// Prefix array storing right most
// index with prefix sums 0, 1, 2
int []pre = { 0, -1, -1 };
// dp array
int[] dp = new int[N];
for(int i = 0; i < N; i++)
{
dp[i] = 0;
}
// Current prefix sum
int C = 0;
for(int i = 0; i < N; i++)
{
C = C + arr[i];
// Calculating the prefix sum modulo 3
C = C % 3;
// We dont have a left pointer
// with prefix sum C
if (pre[C] == -1)
{
if(1 <= i)
dp[i] = dp[i - 1];
// We cannot consider i as
// a right pointer of any segment
}
else
{
// We have a left pointer
// pre[C] with prefix sum C
dp[i] = Math.Max(dp[i - 1],
dp[pre[C]] + 1);
}
// i is the rightmost index of
// prefix sum C
pre[C] = i;
}
return dp[N - 1];
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 2, 36, 1, 9, 2, 0, 1, 8, 1 };
int N = arr.Length;
Console.Write(calculate_maximum_splits(arr, N));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for the above approach
function calculate_maximum_splits(arr, N)
{
// Prefix array storing right most
// index with prefix sums 0, 1, 2
var pre = [0, -1, -1];
var i;
// dp array
var dp = new Array(N);
for(i=0;i<N;i++)
dp[i] = 0;
// Current prefix sum
var C = 0;
for(i = 1; i < N; i++)
{
C = C + arr[i];
// Calculating the prefix sum modulo 3
C = C % 3;
// We dont have a left pointer
// with prefix sum C
if (pre[C] == -1)
{
dp[i] = dp[i - 1];
// We cannot consider i as
// a right pointer of any segment
}
else
{
// We have a left pointer
// pre[C] with prefix sum C
dp[i] = Math.max(dp[i - 1], dp[pre[C]] + 1);
}
// i is the rightmost index of
// prefix sum C
pre[C] = i;
}
document.write(dp[N - 1]);
}
// Driver code
var arr = [2, 36, 1, 9, 2, 0, 1, 8, 1];
var N = arr.length;
calculate_maximum_splits(arr, N);
</script>
4
Complejidad Temporal: O (N)
Espacio Auxiliar: O (N)
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA