Suma máxima de subsecuencias tal que no hay tres consecutivos

Dada una secuencia de números positivos, encuentre la suma máxima que se puede formar que no tenga tres elementos consecutivos presentes.
Ejemplos: 

Input: arr[] = {1, 2, 3}
Output: 5
We can't take three of them, so answer is
2 + 3 = 5

Input: arr[] = {3000, 2000, 1000, 3, 10}
Output: 5013 
3000 + 2000 + 3 + 10 = 5013

Input: arr[] = {100, 1000, 100, 1000, 1}
Output: 2101
100 + 1000 + 1000 + 1 = 2101

Input: arr[] = {1, 1, 1, 1, 1}
Output: 4

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 27

Este problema es principalmente una extensión del siguiente problema.
Suma máxima tal que no hay dos elementos adyacentes
Mantenemos una array auxiliar sum[] (del mismo tamaño que la array de entrada) para encontrar el resultado. 

sum[i] : Stores result for subarray arr[0..i], i.e.,
         maximum possible sum in subarray arr[0..i]
         such that no three elements are consecutive.

sum[0] = arr[0]

// Note : All elements are positive
sum[1] = arr[0] + arr[1]

// We have three cases
// 1) Exclude arr[2], i.e., sum[2] = sum[1]
// 2) Exclude arr[1], i.e., sum[2] = sum[0] + arr[2]
// 3) Exclude arr[0], i.e., sum[2] = arr[1] + arr[2] 
sum[2] = max(sum[1], arr[0] + arr[2], arr[1] + arr[2])

In general,
// We have three cases
// 1) Exclude arr[i],  i.e.,  sum[i] = sum[i-1]
// 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
// 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1] 
sum[i] = max(sum[i-1], sum[i-2] + arr[i],
             sum[i-3] + arr[i] + arr[i-1])

A continuación se muestra la implementación de la idea anterior. 

C++

// C++ program to find the maximum sum such that
// no three are consecutive
#include <bits/stdc++.h>
using namespace std;
   
// Returns maximum subsequence sum such that no three
// elements are consecutive
int maxSumWO3Consec(int arr[], int n)
{
    // Stores result for subarray arr[0..i], i.e.,
    // maximum possible sum in subarray arr[0..i]
    // such that no three elements are consecutive.
    int sum[n];
   
    // Base cases (process first three elements)
    if (n >= 1)
        sum[0] = arr[0];
   
    if (n >= 2)
        sum[1] = arr[0] + arr[1];
   
    if (n > 2)
        sum[2] = max(sum[1], max(arr[1] +
                               arr[2], arr[0] + arr[2]));
   
    // Process rest of the elements
    // We have three cases
    // 1) Exclude arr[i], i.e., sum[i] = sum[i-1]
    // 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
    // 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1]
    for (int i = 3; i < n; i++)
        sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]),
                     arr[i] + arr[i - 1] + sum[i - 3]);
   
    return sum[n - 1];
}
   
// Driver code
int main()
{
    int arr[] = { 100, 1000 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSumWO3Consec(arr, n);
    return 0;
}

C

// C program to find the maximum sum such that
// no three are consecutive
#include <stdio.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// Returns maximum subsequence sum such that no three
// elements are consecutive
int maxSumWO3Consec(int arr[], int n)
{
    // Stores result for subarray arr[0..i], i.e.,
    // maximum possible sum in subarray arr[0..i]
    // such that no three elements are consecutive.
    int sum[n];
 
    // Base cases (process first three elements)
    if (n >= 1)
        sum[0] = arr[0];
 
    if (n >= 2)
        sum[1] = arr[0] + arr[1];
 
    if (n > 2)
        sum[2] = max(sum[1],
                     max(arr[1] + arr[2], arr[0] + arr[2]));
 
    // Process rest of the elements
    // We have three cases
    // 1) Exclude arr[i], i.e., sum[i] = sum[i-1]
    // 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
    // 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] +
    // arr[i-1]
    for (int i = 3; i < n; i++)
        sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]),
                     arr[i] + arr[i - 1] + sum[i - 3]);
 
    return sum[n - 1];
}
 
// Driver code
int main()
{
    int arr[] = { 100, 1000 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d \n", maxSumWO3Consec(arr, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// java program to find the maximum sum
// such that no three are consecutive
import java.io.*;
 
class GFG {
 
    // Returns maximum subsequence sum such that no three
    // elements are consecutive
    static int maxSumWO3Consec(int arr[], int n)
    {
        // Stores result for subarray arr[0..i], i.e.,
        // maximum possible sum in subarray arr[0..i]
        // such that no three elements are consecutive.
        int sum[] = new int[n];
 
        // Base cases (process first three elements)
        if (n >= 1)
            sum[0] = arr[0];
 
        if (n >= 2)
            sum[1] = arr[0] + arr[1];
 
        if (n > 2)
            sum[2] = Math.max(sum[1], Math.max(arr[1] + arr[2], arr[0] + arr[2]));
 
        // Process rest of the elements
        // We have three cases
        // 1) Exclude arr[i], i.e., sum[i] = sum[i-1]
        // 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
        // 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1]
        for (int i = 3; i < n; i++)
            sum[i] = Math.max(Math.max(sum[i - 1], sum[i - 2] + arr[i]),
                              arr[i] + arr[i - 1] + sum[i - 3]);
 
        return sum[n - 1];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 100, 1000, 100, 1000, 1 };
        int n = arr.length;
        System.out.println(maxSumWO3Consec(arr, n));
    }
}
 
// This code is contributed by vt_m

Python3

# Python program to find the maximum sum such that
# no three are consecutive
 
# Returns maximum subsequence sum such that no three
# elements are consecutive
def maxSumWO3Consec(arr, n):
    # Stores result for subarray arr[0..i], i.e.,
    # maximum possible sum in subarray arr[0..i]
    # such that no three elements are consecutive.
    sum = [0 for k in range(n)]
 
    # Base cases (process first three elements)
     
    if n >= 1 :
        sum[0] = arr[0]
     
    if n >= 2 :
        sum[1] = arr[0] + arr[1]
     
    if n > 2 :
        sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]))
 
    # Process rest of the elements
    # We have three cases
    # 1) Exclude arr[i], i.e., sum[i] = sum[i-1]
    # 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
    # 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1]
    for i in range(3, n):
        sum[i] = max(max(sum[i-1], sum[i-2] + arr[i]), arr[i] + arr[i-1] + sum[i-3])
 
    return sum[n-1]
 
# Driver code
arr = [100, 1000, 100, 1000, 1]
n = len(arr)
print (maxSumWO3Consec(arr, n))
 
# This code is contributed by Afzal Ansari

C#

// C# program to find the maximum sum
// such that no three are consecutive
using System;
class GFG {
 
    // Returns maximum subsequence
    // sum such that no three
    // elements are consecutive
    static int maxSumWO3Consec(int[] arr,
                               int n)
    {
        // Stores result for subarray
        // arr[0..i], i.e., maximum
        // possible sum in subarray
        // arr[0..i] such that no
        // three elements are consecutive.
        int[] sum = new int[n];
 
        // Base cases (process
        // first three elements)
        if (n >= 1)
            sum[0] = arr[0];
 
        if (n >= 2)
            sum[1] = arr[0] + arr[1];
 
        if (n > 2)
            sum[2] = Math.Max(sum[1], Math.Max(arr[1] + arr[2], arr[0] + arr[2]));
 
        // Process rest of the elements
        // We have three cases
        // 1) Exclude arr[i], i.e.,
        // sum[i] = sum[i-1]
        // 2) Exclude arr[i-1], i.e.,
        // sum[i] = sum[i-2] + arr[i]
        // 3) Exclude arr[i-2], i.e.,
        // sum[i-3] + arr[i] + arr[i-1]
        for (int i = 3; i < n; i++)
            sum[i] = Math.Max(Math.Max(sum[i - 1],
                                       sum[i - 2] + arr[i]),
                              arr[i] + arr[i - 1] + sum[i - 3]);
 
        return sum[n - 1];
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 100, 1000, 100, 1000, 1 };
        int n = arr.Length;
        Console.Write(maxSumWO3Consec(arr, n));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find the maximum
// sum such that no three are consecutive
 
// Returns maximum subsequence
// sum such that no three
// elements are consecutive
function maxSumWO3Consec($arr, $n)
{
    // Stores result for subarray
    // arr[0..i], i.e., maximum
    // possible sum in subarray
    // arr[0..i] such that no three
    // elements are consecutive$.
    $sum = array();
 
    // Base cases (process
    // first three elements)
    if ( $n >= 1)
    $sum[0] = $arr[0];
     
    if ($n >= 2)
    $sum[1] = $arr[0] + $arr[1];
     
    if ( $n > 2)
    $sum[2] = max($sum[1], max($arr[1] + $arr[2],
                            $arr[0] + $arr[2]));
 
    // Process rest of the elements
    // We have three cases
    // 1) Exclude arr[i], i.e.,
    // sum[i] = sum[i-1]
    // 2) Exclude arr[i-1], i.e.,
    // sum[i] = sum[i-2] + arr[i]
    // 3) Exclude arr[i-2], i.e.,
    // sum[i-3] + arr[i] + arr[i-1]
    for ($i = 3; $i < $n; $i++)
        $sum[$i] = max(max($sum[$i - 1],
                        $sum[$i - 2] + $arr[$i]),
                        $arr[$i] + $arr[$i - 1] +
                                    $sum[$i - 3]);
 
    return $sum[$n-1];
}
 
// Driver code
$arr = array(100, 1000, 100, 1000, 1);
$n =count($arr);
echo maxSumWO3Consec($arr, $n);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// JavaScript program to find the maximum sum
// such that no three are consecutive
 
    // Returns maximum subsequence sum such that no three
    // elements are consecutive
    function maxSumWO3Consec(arr, n)
    {
        // Stores result for subarray arr[0..i], i.e.,
        // maximum possible sum in subarray arr[0..i]
        // such that no three elements are consecutive.
        let sum = [];
  
        // Base cases (process first three elements)
        if (n >= 1)
            sum[0] = arr[0];
  
        if (n >= 2)
            sum[1] = arr[0] + arr[1];
  
        if (n > 2)
            sum[2] = Math.max(sum[1], Math.max(arr[1] + arr[2], arr[0] + arr[2]));
  
        // Process rest of the elements
        // We have three cases
        // 1) Exclude arr[i], i.e., sum[i] = sum[i-1]
        // 2) Exclude arr[i-1], i.e., sum[i] = sum[i-2] + arr[i]
        // 3) Exclude arr[i-2], i.e., sum[i-3] + arr[i] + arr[i-1]
        for (let i = 3; i < n; i++)
            sum[i] = Math.max(Math.max(sum[i - 1], sum[i - 2] + arr[i]),
                              arr[i] + arr[i - 1] + sum[i - 3]);
  
        return sum[n - 1];
    }
     
// Driver Code
        let arr = [ 100, 1000, 100, 1000, 1 ];
        let n = arr.length;
        document.write(maxSumWO3Consec(arr, n));
 
// This code is contributed by chinmoy1997pal.
</script>

Producción: 

1100

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(n)
Otro enfoque: (usando la recursividad)  

C++

// C++ program to find the maximum sum such that
// no three are consecutive using recursion.
#include<bits/stdc++.h>
using namespace std;
 
// Returns maximum subsequence sum such that no three
// elements are consecutive
int maxSum(int arr[], int i, vector<int> &dp)
{
    // base case
    if (i < 0)
        return 0;
 
    // this condition check is necessary to avoid segmentation fault at line 21
    if (i == 0)
        return arr[i];
 
    // returning maxSum for already processed indexes of array
    if (dp[i] != -1)
        return dp[i];
 
    // including current element and the next consecutive element in subsequence
    int a = arr[i] + arr[i - 1] + maxSum(arr, i - 3, dp);
 
    // not including the current element in subsequence
    int b = maxSum(arr, i - 1, dp);
 
    // including current element but skipping next consecutive element
    int c = arr[i] + maxSum(arr, i - 2, dp);
 
    // returning the max of above 3 cases
    return dp[i] = max(a, max(b, c));
}
 
// Driver code
int main()
{
    int arr[] = {100, 1000, 100, 1000, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<int> dp(n, -1);  // declaring and initializing dp vector
    cout << maxSum(arr, n - 1, dp) << endl;
 
    return 0;
}
// This code is contributed by Ashish Kumar Yadav

Java

// Java program to find the maximum
// sum such that no three are
// consecutive using recursion.
import java.util.Arrays;
 
class GFG
{
     
static int arr[] = {100, 1000, 100, 1000, 1};
static int sum[] = new int[10000];
 
// Returns maximum subsequence
// sum such that no three
// elements are consecutive
static int maxSumWO3Consec(int n)
{
    if(sum[n] != -1)
        return sum[n];
     
    //Base cases (process first three elements)
     
    if(n == 0)
        return sum[n] = 0;
     
    if(n == 1)
        return sum[n] = arr[0];
     
    if(n == 2)
        return sum[n] = arr[1] + arr[0];
     
    // Process rest of the elements
    // We have three cases
    return sum[n] = Math.max(Math.max(maxSumWO3Consec(n - 1),
                    maxSumWO3Consec(n - 2) + arr[n]),
                    arr[n] + arr[n - 1] + maxSumWO3Consec(n - 3));
     
     
}
 
// Driver code
public static void main(String[] args)
{
    int n = arr.length;
        Arrays.fill(sum, -1);
    System.out.println(maxSumWO3Consec(n));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to find the maximum
# sum such that no three are consecutive
# using recursion.
arr = [100, 1000, 100, 1000, 1]
sum = [-1] * 10000
 
# Returns maximum subsequence sum such
# that no three elements are consecutive
def maxSumWO3Consec(n) :
 
    if(sum[n] != -1):
        return sum[n]
     
    # 3 Base cases (process first
    # three elements)
    if(n == 0) :
        sum[n] = 0
        return sum[n]
     
    if(n == 1) :
        sum[n] = arr[0]
        return sum[n]
     
    if(n == 2) :
        sum[n] = arr[1] + arr[0]
        return sum[n]
     
    # Process rest of the elements
    # We have three cases
    sum[n] = max(max(maxSumWO3Consec(n - 1),
                     maxSumWO3Consec(n - 2) + arr[n-1]),
                     arr[n-1] + arr[n - 2] +
                     maxSumWO3Consec(n - 3))
     
    return sum[n]
 
# Driver code
if __name__ == "__main__" :
 
    n = len(arr)
     
    print(maxSumWO3Consec(n))
 
# This code is contributed by Ryuga

C#

// C# program to find the maximum
// sum such that no three are
// consecutive using recursion.
using System;
 
class GFG
{
 
    static int []arr = {100, 1000,
                        100, 1000, 1};
    static int []sum = new int[10000];
 
    // Returns maximum subsequence
    // sum such that no three
    // elements are consecutive
    static int maxSumWO3Consec(int n)
    {
        if(sum[n] != -1)
            return sum[n];
 
        //Base cases (process first
        // three elements)
        if(n == 0)
            return sum[n] = 0;
 
        if(n == 1)
            return sum[n] = arr[0];
 
        if(n == 2)
            return sum[n] = arr[1] + arr[0];
 
        // Process rest of the elements
        // We have three cases
        return sum[n] = Math.Max(Math.Max(maxSumWO3Consec(n - 1),
                        maxSumWO3Consec(n - 2) + arr[n]),
                        arr[n] + arr[n - 1] + maxSumWO3Consec(n - 3));
 
 
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int n = arr.Length;
        for(int i = 0; i < sum.Length; i++)
            sum[i] = -1;
        Console.WriteLine(maxSumWO3Consec(n));
    }
}
 
// This code is contributed by 29AjayKumar

PHP

<?php
// PHP program to find the maximum sum such that
// no three are consecutive using recursion.
$arr = array(100, 1000, 100, 1000, 1);
$sum = array_fill(0, count($arr) + 1, -1);
 
// Returns maximum subsequence sum such that
// no three elements are consecutive
function maxSumWO3Consec($n)
{
    global $sum,$arr;
    if($sum[$n] != -1)
        return $sum[$n];
     
    // Base cases (process first three elements)
    if($n == 0)
        return $sum[$n] = 0;
     
    if($n == 1)
        return $sum[$n] = $arr[0];
     
    if($n == 2)
        return $sum[$n] = $arr[1] + $arr[0];
     
    // Process rest of the elements
    // We have three cases
    return $sum[$n] = max(max(maxSumWO3Consec($n - 1),
                              maxSumWO3Consec($n - 2) + $arr[$n]),
                                              $arr[$n] + $arr[$n - 1] +
                              maxSumWO3Consec($n - 3));
}
 
// Driver code
$n = count($arr);
echo maxSumWO3Consec($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
    // JavaScript program to find the maximum
    // sum such that no three are
    // consecutive using recursion.
     
    let arr = [100, 1000, 100, 1000, 1];
    let sum = new Array(10000);
    for(let i = 0; i < 10000; i++)
    {
        sum[i] = -1;
    }
 
    // Returns maximum subsequence
    // sum such that no three
    // elements are consecutive
    function maxSumWO3Consec(n)
    {
        if(sum[n] != -1)
        {
            return sum[n];   
        }
 
        //Base cases (process first three elements)
 
        if(n == 0)
        {
            return sum[n] = 0;
        }
            
        if(n == 1)
        {
            return sum[n] = arr[0];
        }
             
 
        if(n == 2)
        {
            return sum[n] = arr[1] + arr[0];
        }
             
 
        // Process rest of the elements
        // We have three cases        
          return sum[n] =
        500+Math.max(Math.max(maxSumWO3Consec(n - 1),
        maxSumWO3Consec(n - 2) + arr[n]),
        arr[n] + arr[n - 1] + maxSumWO3Consec(n - 3));
    }
     
    let n = arr.length - 1;
    document.write(maxSumWO3Consec(n) + 1);
 
</script>

Producción: 

2101

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(n)
Este artículo es una contribución de Roshni Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *