Dada una array A[] de N números positivos, la tarea es encontrar la suma máxima que se puede formar que no tenga tres elementos consecutivos presentes.
Ejemplos:
Entrada: A[] = {1, 2, 3}, N=3
Salida: 5
Explicación: Tres de ellos no se pueden tomar juntos, por lo que la respuesta es 2 + 3 = 5Entrada: A[] = {3000, 2000, 1000, 3, 10}, N=5
Salida: 5013
Aquí se ha discutido un enfoque O(N) que toma el espacio auxiliar O ( N ) . Esto se puede optimizar aún más con el siguiente enfoque que ocupa O(1) espacio adicional.
O(1) Enfoque espacial: del enfoque anterior, podemos concluir que para calcular sum[i], solo los valores de sum[i-1], sum[i-2] y sum[i-3] son relevantes. Esta observación puede ayudar a descartar la array de suma por completo y, en su lugar, solo mantener algunas variables para resolver el problema usando el espacio auxiliar O(1).
Siga los pasos a continuación para resolver el problema:
- Inicialice las siguientes variables a utilizar:
- suma: Esto almacena la suma final de modo que no haya tres elementos consecutivos.
- primero: Esto almacena la suma de la subsecuencia hasta el índice i-1 .
- segundo: Esto almacena la suma de la subsecuencia hasta el índice i-2 .
- tercero: Esto almacena la suma de la subsecuencia hasta el índice i-3 .
- Si N<3 , la respuesta sería la suma de todos los elementos ya que no habrá consecutivos.
- De lo contrario, haga lo siguiente:
- Inicializar tercero con A[0]
- Inicializar segundo con A[0]+A[1]
- Inicializar primero con max(segundo, A[1]+A[2])
- Inicialice la suma con el máximo entre primero , segundo y tercero .
- Iterar de 3 a N-1 y hacer lo siguiente para cada índice i actual :
- Pueden darse los siguientes tres casos:
- Excluir A[i], es decir , suma = primero
- Excluir A[i-1], es decir, suma = segundo + A[i]
- Excluir A[i-2] , es decir, suma = tercero + A[i] + A[i-1]
- Por lo tanto, la suma se actualiza como el máximo entre primero , (segundo+A[i]) y (tercero+A[i]+A[i-1])
- Actualice el tercero con el segundo , el segundo con el primero y el primero con la suma .
- Pueden darse los siguientes tres casos:
- Finalmente, devuelva la suma .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum subsequence sum such
// that no three elements are consecutive
int maxSumWO3Consec(int A[], int N)
{
// when N is 1, answer would be the only element present
if (N == 1)
return A[0];
// when N is 2, answer would be sum of elements
if (N == 2)
return A[0] + A[1];
// variable to store sum up to i - 3
int third = A[0];
// variable to store sum up to i - 2
int second = third + A[1];
// variable to store sum up to i - 1
int first = max(second, A[1] + A[2]);
// variable to store the final sum of the subsequence
int sum = max(max(third, second), first);
for (int i = 3; i < N; i++) {
// find the maximum subsequence sum up to index i
sum = max(max(first, second + A[i]),
third + A[i] + A[i - 1]);
// update first, second and third
third = second;
second = first;
first = sum;
}
// return ans;
return sum;
}
// Driver code
int main()
{
// Input
int A[] = { 3000, 2000, 1000, 3, 10 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
cout << maxSumWO3Consec(A, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to calculate the maximum subsequence sum
// such
// that no three elements are consecutive
public static int maxSumWO3Consec(int A[], int N)
{
// when N is 1, answer would be the only element
// present
if (N == 1)
return A[0];
// when N is 2, answer would be sum of elements
if (N == 2)
return A[0] + A[1];
// variable to store sum up to i - 3
int third = A[0];
// variable to store sum up to i - 2
int second = third + A[1];
// variable to store sum up to i - 1
int first = Math.max(second, A[1] + A[2]);
// variable to store the final sum of the
// subsequence
int sum = Math.max(Math.max(third, second), first);
for (int i = 3; i < N; i++)
{
// find the maximum subsequence sum up to index
// i
sum = Math.max(Math.max(first, second + A[i]),
third + A[i] + A[i - 1]);
// update first, second and third
third = second;
second = first;
first = sum;
}
// return ans;
return sum;
}
public static void main(String[] args)
{
// Input
int A[] = { 3000, 2000, 1000, 3, 10 };
int N = A.length;
// Function call
int res = maxSumWO3Consec(A, N);
System.out.println(res);
}
}
//This code is contributed by Potta Lokesh
Python3
# Python 3 implementation for the above approach # Function to calculate the maximum subsequence sum such # that no three elements are consecutive def maxSumWO3Consec(A, N): # when N is 1, answer would be the only element present if (N == 1): return A[0] # when N is 2, answer would be sum of elements if (N == 2): return A[0] + A[1] # variable to store sum up to i - 3 third = A[0] # variable to store sum up to i - 2 second = third + A[1] # variable to store sum up to i - 1 first = max(second, A[1] + A[2]) # variable to store the final sum of the subsequence sum = max(max(third, second), first) for i in range(3,N,1): # find the maximum subsequence sum up to index i sum = max(max(first, second + A[i]), third + A[i] + A[i - 1]) # update first, second and third third = second second = first first = sum # return ans; return sum # Driver code if __name__ == '__main__': # Input A = [3000, 2000, 1000, 3, 10] N = len(A) # Function call print(maxSumWO3Consec(A, N)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG {
// Function to calculate the maximum subsequence sum
// such
// that no three elements are consecutive
public static int maxSumWO3Consec(int[] A, int N)
{
// when N is 1, answer would be the only element
// present
if (N == 1)
return A[0];
// when N is 2, answer would be sum of elements
if (N == 2)
return A[0] + A[1];
// variable to store sum up to i - 3
int third = A[0];
// variable to store sum up to i - 2
int second = third + A[1];
// variable to store sum up to i - 1
int first = Math.Max(second, A[1] + A[2]);
// variable to store the final sum of the
// subsequence
int sum = Math.Max(Math.Max(third, second), first);
for (int i = 3; i < N; i++) {
// find the maximum subsequence sum up to index
// i
sum = Math.Max(Math.Max(first, second + A[i]),
third + A[i] + A[i - 1]);
// update first, second and third
third = second;
second = first;
first = sum;
}
// return ans;
return sum;
}
// Driver Code
public static void Main()
{
// Input
int[] A = { 3000, 2000, 1000, 3, 10 };
int N = A.Length;
// Function call
int res = maxSumWO3Consec(A, N);
Console.Write(res);
}
}
Javascript
<script>
// JavaScript implementation for the above approach
// Function to calculate the maximum subsequence sum such
// that no three elements are consecutive
function maxSumWO3Consec(A, N)
{
// when N is 1, answer would be the only element present
if (N == 1)
return A[0];
// when N is 2, answer would be sum of elements
if (N == 2)
return A[0] + A[1];
// variable to store sum up to i - 3
let third = A[0];
// variable to store sum up to i - 2
let second = third + A[1];
// variable to store sum up to i - 1
let first = Math.max(second, A[1] + A[2]);
// variable to store the final sum of the subsequence
let sum = Math.max(Math.max(third, second), first);
for (let i = 3; i < N; i++) {
// find the maximum subsequence sum up to index i
sum = Math.max(Math.max(first, second + A[i]),
third + A[i] + A[i - 1]);
// update first, second and third
third = second;
second = first;
first = sum;
}
// return ans;
return sum;
}
// Driver code
// Input
let A = [3000, 2000, 1000, 3, 10];
let N = A.length;
// Function call
document.write(maxSumWO3Consec(A, N));
//This code is contributed by Potta Lokesh
</script>
Producción:
5013
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ganapati_biswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA