Suma máxima tal que no hay dos elementos adyacentes – Part 1

Dada una array arr[] de números positivos, la tarea es encontrar la suma máxima de una subsecuencia con la restricción de que no debe haber 2 números adyacentes en la secuencia en la array.

Ejemplos: 

C++

// C++ code to implement the approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the maximum sum
int findMaxSum(vector<int> arr, int N)
{
    // Declare dp array
    int dp[N][2];
    if (N == 1) {
        return arr[0];
    }
    
    // Initialize the values in dp array
    dp[0][0] = 0;
    dp[0][1] = arr[0];
    
    // Loop to find the maximum possible sum
    for (int i = 1; i < N; i++) {
        dp[i][1] = dp[i - 1][0] + arr[i];
        dp[i][0] = max(dp[i - 1][1], 
                       dp[i - 1][0]);
    }
    
    // Return the maximum sum
    return max(dp[N - 1][0], dp[N - 1][1]);
}
  
// Driver Code
int main()
{
    // Creating the array
    vector<int> arr = { 5, 5, 10, 100, 10, 5 };
    int N = arr.size();
  
    // Function call
    cout << findMaxSum(arr, N) << endl;
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
  
class GFG
{
  
  // Function to find the maximum sum
  static int findMaxSum(int[] arr, int N)
  {
    // Declare dp array
    int[][] dp = new int[N][2];
    if (N == 1) {
      return arr[0];
    }
  
    // Initialize the values in dp array
    dp[0][0] = 0;
    dp[0][1] = arr[0];
  
    // Loop to find the maximum possible sum
    for (int i = 1; i < N; i++) {
      dp[i][1] = dp[i - 1][0] + arr[i];
      dp[i][0] = Math.max(dp[i - 1][1],
                          dp[i - 1][0]);
    }
  
    // Return the maximum sum
    return Math.max(dp[N - 1][0], dp[N - 1][1]);
  }
  
  
  // Driver Code
  public static void main(String args[])
  {
  
    // Creating the array
    int[] arr = { 5, 5, 10, 100, 10, 5 };
    int N = arr.length;
  
    // Function call
    System.out.println(findMaxSum(arr, N));
  }
}
  
// This code is contributed by shinjanpatra

Python3

# Python code to implement the approach
  
# Function to find the maximum sum
def findMaxSum(arr, N):
  
    # Declare dp array
    dp = [[0 for i in range(2)] for j in range(N)]
      
    if (N == 1): 
        return arr[0]
    
    # Initialize the values in dp array
    dp[0][0] = 0
    dp[0][1] = arr[0]
    
    # Loop to find the maximum possible sum
    for i in range(1,N):
        dp[i][1] = dp[i - 1][0] + arr[i]
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])
    
    # Return the maximum sum
    return max(dp[N - 1][0], dp[N - 1][1])
  
# Driver Code
  
# Creating the array
arr = [ 5, 5, 10, 100, 10, 5 ]
N = len(arr)
  
# Function call
print(findMaxSum(arr, N))
  
# This code is contribute by shinjanpatra

C#

// C# program for above approach
using System;
  
class GFG{
      
// Function to find the maximum sum
int findMaxSum(int[] arr,int n)
{
      
    // Declare dp array
    int [,] dp = new int [n,2];
    if (n == 1) {
        return arr[0];
    }
     
    // Initialize the values in dp array
    dp[0,0] = 0;
    dp[0,1] = arr[0];
     
    // Loop to find the maximum possible sum
    for (int i = 1; i < n; i++) {
        dp[i,1] = dp[i - 1,0] + arr[i];
        dp[i,0] = Math.Max(dp[i - 1,1],
                       dp[i - 1,0]);
    }
     
    // Return the maximum sum
    return Math.Max(dp[n - 1,0], dp[n - 1,1]);
}
  
// Driver code
static public void Main ()
{
    GFG small = new GFG();
    int[] arr = {5, 5, 10, 100, 10, 5};
    int n = arr.Length;
      
    // Function Call
    Console.WriteLine(small.findMaxSum(arr,n));
}
}
  
// This code is contributed by Aarti_Rathi

Javascript

<script>
  
// JavaScript code to implement the approach
  
// Function to find the maximum sum
function findMaxSum(arr, N)
{
  
    // Declare dp array
    let dp = new Array(N);
    for(let i = 0; i < N; i++)
    {
        dp[i] = new Array(2);
    }
    if (N == 1) 
    {
        return arr[0];
    }
    
    // Initialize the values in dp array
    dp[0][0] = 0;
    dp[0][1] = arr[0];
    
    // Loop to find the maximum possible sum
    for (let i = 1; i < N; i++) {
        dp[i][1] = dp[i - 1][0] + arr[i];
        dp[i][0] = Math.max(dp[i - 1][1], 
                       dp[i - 1][0]);
    }
    
    // Return the maximum sum
    return Math.max(dp[N - 1][0], dp[N - 1][1]);
}
  
// Driver Code
  
// Creating the array
let arr = [ 5, 5, 10, 100, 10, 5 ];
let N = arr.length;
  
// Function call
document.write(findMaxSum(arr, N),"</br>");
  
/*This code is contribute by shinjanpatra */
  
</script>

C++

// C++ code to implement the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to return max sum such that 
// no two elements are adjacent 
int FindMaxSum(vector<int> arr, int n)
{
    int incl = arr[0];
    int excl = 0;
    int excl_new;
    int i;
  
    for (i = 1; i < n; i++) {
        // Current max excluding i
        excl_new = max(incl, excl);
  
        // Current max including i
        incl = excl + arr[i];
        excl = excl_new;
    }
  
    // Return max of incl and excl
    return max(incl, excl);
}
  
// Driver code
int main()
{
    vector<int> arr = { 5, 5, 10, 100, 10, 5 };
    int N = arr.size();
  
    // Function call
    cout << FindMaxSum(arr, N);
    return 0;
}
// This approach is contributed by Debanjan

C

// C code to implement the approach
  
#include <stdio.h>
  
// Function to return max sum such that
// no two elements are adjacent
int findMaxSum(int arr[], int n)
{
    int incl = arr[0];
    int excl = 0;
    int excl_new;
    int i;
  
    for (i = 1; i < n; i++) {
          
        // Current max excluding i
        excl_new = (incl > excl) ? incl : excl;
  
        // Current max including i
        incl = excl + arr[i];
        excl = excl_new;
    }
  
    // Return max of incl and excl
    return ((incl > excl) ? incl : excl);
}
  
// Driver code
int main()
{
    int arr[] = { 5, 5, 10, 100, 10, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
      
    // Function call
    printf("%d", findMaxSum(arr, N));
    return 0;
}

Java

// Java code to implement the approach
  
import java.lang.*;
import java.util.*;
  
class MaximumSum {
    // Function to return max sum such that
    // no two elements are adjacent
    int findMaxSum(int arr[], int n)
    {
        int incl = arr[0];
        int excl = 0;
        int excl_new;
        int i;
  
        for (i = 1; i < n; i++) {
            // Current max excluding i
            excl_new = Math.max(incl, excl);
  
            // Current max including i
            incl = excl + arr[i];
            excl = excl_new;
        }
  
        // Return max of incl and excl
        return Math.max(incl, excl);
    }
  
    // Driver code
    public static void main(String[] args)
    {
        MaximumSum sum = new MaximumSum();
        int arr[] = new int[] { 5, 5, 10, 100, 
                                10, 5 };
        int N = arr.length;
  
        // Function call
        System.out.println(
            sum.findMaxSum(arr, arr.length));
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python code to implement the approach
  
# Function to return max sum such that 
# no two elements are adjacent
def findMaxSum(arr, n):
    incl = 0
    excl = 0   
    for i in arr:
          
        # Current max excluding i
        new_excl = max (excl, incl)
          
        # Current max including i
        incl = excl + i
        excl = new_excl
      
    # Return max of incl and excl
    return max(excl, incl)
  
# Driver code
if __name__ == "__main__":
    arr = [5, 5, 10, 100, 10, 5]
    N = 6
      
    # Function call
    print (findMaxSum(arr, N))
  
# This code is contributed by Kalai Selvan

C#

// C# code to implement the approach
  
using System;
  
class GFG {    
    // Function to return max sum such
    // that no two elements are adjacent
    static int findMaxSum(int []arr, int n)
    {
        int incl = arr[0];
        int excl = 0;
        int excl_new;
        int i;
  
        for (i = 1; i < n; i++) {
            // Current max excluding i
            excl_new = (incl > excl) ? 
                            incl : excl;
  
            // Current max including i
            incl = excl + arr[i];
            excl = excl_new;
        }
  
        // Return max of incl and excl
        return ((incl > excl) ? 
                            incl : excl);
    }
  
    // Driver code
    public static void Main()
    {
        int []arr = new int[]{5, 5, 10,
                              100, 10, 5};
        int N = arr.Length;
  
        // Function call
        Console.Write(findMaxSum(arr, N));
    }
}
  
// This code has been contributed by
// nitin mittal

PHP

<?php
// PHP code to find Maximum sum 
// such that no two elements 
// are adjacent
  
/* Function to return max sum
   such that no two elements
   are adjacent */
function FindMaxSum($arr, $n)
{
    $incl = $arr[0];
    $excl = 0;
    $excl_new;
    $i;
  
for ($i = 1; $i <$n; $i++)
{
      
    // current max excluding i 
    $excl_new = ($incl > $excl)? $incl: $excl;
  
    // current max including i 
    $incl = $excl + $arr[$i];
    $excl = $excl_new;
}
  
// return max of incl and excl 
return (($incl > $excl)? $incl : $excl);
}
  
// Driver Code
$arr = array(5, 5, 10, 100, 10, 5);
$n = sizeof($arr);
echo FindMaxSum($arr, $n);
      
// This code is contributed by Ajit
?>

Javascript

<script>
  
// Javascript program for the above approach
  
// Function to return max sum such that
// no two elements are adjacent 
function FindMaxSum(arr, n)
{
    let incl = arr[0];
    let excl = 0;
    let excl_new;
    let i;
  
    for(i = 1; i < n; i++)
    {
          
        // Current max excluding i 
        excl_new = (incl > excl) ? incl : excl;
  
        // Current max including i 
        incl = excl + arr[i];
        excl = excl_new;
    }
  
    // Return max of incl and excl 
    return ((incl > excl) ? incl : excl);
}
  
// Driver code
let arr = [ 5, 5, 10, 100, 10, 5 ];
  
document.write(FindMaxSum(arr, arr.length));
  
// This code is contributed by Mayank Tyagi
  
</script>

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 *