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