Dada una array arr[] de números positivos, encuentre la suma máxima de una subsecuencia con la restricción de que no deben ser adyacentes 2 números en la secuencia en la array donde se supone que el último y el primer elemento son adyacentes.
Ejemplos:
Entrada: arr[] = {3, 5, 3}
Salida: 5
Explicación:
No podemos tomar el primer y el último elemento porque se consideran adyacentes, por lo que la salida es 5.
Entrada arr[] = {1, 223, 41, 4, 414, 5, 16}
Salida: 653
Explicación:
Tomando elementos del índice 1, 4 y 6 obtenemos la suma máxima como 653.
Enfoque: La idea es utilizar el algoritmo de Memorización para resolver el problema mencionado anteriormente. La observación más importante es que el primero y el último elemento nunca pueden elegirse juntos . Entonces, podemos dividir el problema en dos partes:
- La suma máxima que podemos obtener del índice 0 al tamaño de la array: 2
- La suma máxima que podemos obtener del índice 1 al tamaño de la array: 1
La respuesta será el máximo de estas dos sumas que se puede resolver mediante Programación Dinámica .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum sum
// in circular array such that
// no two elements are adjacent
#include <bits/stdc++.h>
using namespace std;
// Store the maximum possible at each index
vector<int> dp;
int maxSum(int i, vector<int>& subarr)
{
// When i exceeds the index of the
// last element simply return 0
if (i >= subarr.size())
return 0;
// If the value has already been calculated,
// directly return it from the dp array
if (dp[i] != -1)
return dp[i];
// The next states are don't take
// this element and go to (i + 1)th state
// else take this element
// and go to (i + 2)th state
return dp[i]
= max(maxSum(i + 1, subarr),
subarr[i]
+ maxSum(i + 2, subarr));
}
// function to find the max value
int Func(vector<int> arr)
{
vector<int> subarr = arr;
// subarr contains elements
// from 0 to arr.size() - 2
subarr.pop_back();
// Initializing all the values with -1
dp.resize(subarr.size(), -1);
// Calculating maximum possible
// sum for first case
int max1 = maxSum(0, subarr);
subarr = arr;
// subarr contains elements
// from 1 to arr.size() - 1
subarr.erase(subarr.begin());
dp.clear();
// Re-initializing all values with -1
dp.resize(subarr.size(), -1);
// Calculating maximum possible
// sum for second case
int max2 = maxSum(0, subarr);
// Printing the maximum between them
cout << max(max1, max2) << endl;
}
// Driver code
int main()
{
vector<int> arr = { 1, 2, 3, 1 };
Func(arr);
return 0;
}
Java
// Java program to find maximum sum
// in circular array such that
// no two elements are adjacent
import java.util.*;
class GFG{
// Store the maximum
// possible at each index
static Vector<Integer> dp =
new Vector<>();
static int maxSum(int i,
Vector<Integer> subarr)
{
// When i exceeds the index of the
// last element simply return 0
if (i >= subarr.size())
return 0;
// If the value has already
// been calculated, directly
// return it from the dp array
if (dp.get(i) != -1)
return dp.get(i);
// The next states are don't take
// this element and go to (i + 1)th state
// else take this element
// and go to (i + 2)th state
dp.add(i, Math.max(maxSum(i + 1, subarr),
subarr.get(i) +
maxSum(i + 2, subarr)));
return dp.get(i);
}
// function to find the max value
static void Func(Vector<Integer> arr)
{
Vector<Integer> subarr =
new Vector<>();
subarr.addAll(arr);
// subarr contains elements
// from 0 to arr.size() - 2
subarr.remove(subarr.size() - 1);
// Initializing all the values with -1
dp.setSize(subarr.size());
Collections.fill(dp, -1);
// Calculating maximum possible
// sum for first case
int max1 = maxSum(0, subarr);
subarr = arr;
// subarr contains elements
// from 1 to arr.size() - 1
subarr.remove(0);
dp.clear();
// Re-initializing all values with -1
dp.setSize(subarr.size());
Collections.fill(dp, -1);
// Calculating maximum possible
// sum for second case
int max2 = maxSum(0, subarr);
// Printing the maximum between them
System.out.print(Math.max(max1, max2) + "\n");
}
// Driver code
public static void main(String[] args)
{
Vector<Integer> arr =new Vector<>();
arr.add(1);
arr.add(2);
arr.add(3);
arr.add(1);
Func(arr);
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to find maximum sum # in circular array such that # no two elements are adjacent # Store the maximum possible at each index dp = [] def maxSum(i, subarr): # When i exceeds the index of the # last element simply return 0 if (i >= len(subarr)): return 0 # If the value has already been # calculated, directly return # it from the dp array if (dp[i] != -1): return dp[i] # The next states are don't take # this element and go to (i + 1)th state # else take this element # and go to (i + 2)th state dp[i] = max(maxSum(i + 1, subarr), subarr[i] + maxSum(i + 2, subarr)) return dp[i] # function to find the max value def Func(arr): subarr = arr # subarr contains elements # from 0 to arr.size() - 2 subarr.pop() global dp # Initializing all the values with -1 dp= [-1] * (len(subarr)) # Calculating maximum possible # sum for first case max1 = maxSum(0, subarr) subarr = arr # subarr contains elements # from 1 to arr.size() - 1 subarr = subarr[:] del dp # Re-initializing all values with -1 dp = [-1] * (len(subarr)) # Calculating maximum possible # sum for second case max2 = maxSum(0, subarr) # Printing the maximum between them print(max(max1, max2)) # Driver code if __name__ == "__main__": arr = [1, 2, 3, 1] Func(arr) # This code is contributed by Chitranayal
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Store the maximum
// possible at each index
static List<int> dp = new List<int>();
static int maxSum(int i, List<int> subarr)
{
// When i exceeds the index of the
// last element simply return 0
if (i >= subarr.Count)
return 0;
// If the value has already
// been calculated, directly
// return it from the dp array
if (dp[i] != -1)
return dp[i];
// The next states are don't take
// this element and go to (i + 1)th state
// else take this element
// and go to (i + 2)th state
dp[i] = Math.Max(maxSum(i + 1, subarr), subarr[i] + maxSum(i + 2, subarr));
return dp[i];
}
// function to find the max value
static void Func(List<int> arr)
{
List<int> subarr = new List<int>(arr);
// subarr contains elements
// from 0 to arr.size() - 2
subarr.RemoveAt(subarr.Count - 1);
// Initializing all the values with -1
for(int i = 0 ; i < subarr.Count ; i++){
dp.Add(-1);
}
// Calculating maximum possible
// sum for first case
int max1 = maxSum(0, subarr);
subarr = arr;
// subarr contains elements
// from 1 to arr.size() - 1
subarr.RemoveAt(0);
dp.Clear();
// Re-initializing all values with -1
for(int i = 0 ; i < subarr.Count ; i++){
dp.Add(-1);
}
// Calculating maximum possible
// sum for second case
int max2 = maxSum(0, subarr);
// Printing the maximum between them
Console.WriteLine(Math.Max(max1, max2));
}
// Driver code
public static void Main(string[] args){
List<int> arr =new List<int>();
arr.Add(1);
arr.Add(2);
arr.Add(3);
arr.Add(1);
Func(arr);
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// Javascript program to find maximum sum
// in circular array such that
// no two elements are adjacent
// Store the maximum
// possible at each index
let dp =[];
function maxSum(i,subarr)
{
// When i exceeds the index of the
// last element simply return 0
if (i >= subarr.length)
return 0;
// If the value has already
// been calculated, directly
// return it from the dp array
if (dp[i] != -1)
return dp[i];
// The next states are don't take
// this element and go to (i + 1)th state
// else take this element
// and go to (i + 2)th state
dp[i] = Math.max(maxSum(i + 1, subarr),
subarr[i] +
maxSum(i + 2, subarr));
return dp[i];
}
// function to find the max value
function Func(arr)
{
let subarr =arr;
// subarr contains elements
// from 0 to arr.size() - 2
subarr.pop();
// Initializing all the values with -1
dp=new Array(subarr.length);
for(let i=0;i<subarr.length;i++)
{
dp[i]=-1;
}
// Calculating maximum possible
// sum for first case
let max1 = maxSum(0, subarr);
subarr = arr;
// subarr contains elements
// from 1 to arr.size() - 1
subarr.shift();
dp=[];
// Re-initializing all values with -1
dp=new Array(subarr.length);
for(let i=0;i<dp.length;i++)
{
dp[i]=-1;
}
// Calculating maximum possible
// sum for second case
let max2 = maxSum(0, subarr);
// Printing the maximum between them
document.write(Math.max(max1, max2) + "<br>");
}
// Driver code
let arr=[1,2,3,1];
Func(arr);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
4
Complejidad temporal: O(N)
Complejidad espacial auxiliar: O(N)
Método 2: Tabulación
C++
// C++ program to find maximum sum
// in circular array such that
// no two elements are adjacent
#include <bits/stdc++.h>
using namespace std;
int findMax(vector<int> arr, int n, vector<int> &dp){
dp[0] = arr[0] ;
for(int i = 1 ; i <= n ; i++ ){
int pick = arr[i];
if(i > 1){
pick += dp[i-2] ;
}
int notPick = 0 + dp[i-1] ;
dp[i] = max(pick, notPick) ;
}
return dp[n] ;
}
// function to find the max value
int Func(vector<int> nums)
{
if(nums.size() == 1){
return nums[0] ;
}
// First and last element together
// can never be in the answer
vector<int> v1, v2 ;
int n = nums.size() ;
// Store the maximum possible at each index
vector<int> dp(nums.size() , -1) ;
for(int i = 0 ; i < n ; i++ ){
if(i != 0) v1.push_back(nums[i] ) ;
if(i != n-1) v2.push_back(nums[i] ) ;
}
// calculate the max when
// first element was considered
// and when last element was considered
cout<< max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp)) ;
}
// Driver code
int main()
{
vector<int> arr = { 1, 2, 3, 1 };
Func(arr);
return 0;
}
Python3
# Python program implementation def findMax(arr, n, dp): dp[0] = arr[0] for i in range(1,n+1): pick = arr[i] if(i > 1): pick += dp[i-2] notPick = 0 + dp[i-1] dp[i] = max(pick, notPick) return dp[n] # function to find the max value def Func(nums): if(len(nums) == 1): return nums[0] # First and last element together # can never be in the answer v1 = [] v2 = [] n = len(nums) # Store the maximum possible at each index dp = [-1 for i in range(len(nums))] for i in range(n): if(i != 0): v1.append(nums[i]) if(i != n-1): v2.append(nums[i]) # calculate the max when # first element was considered # and when last element was considered print(max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp))) # Driver code arr = [ 1, 2, 3, 1 ] Func(arr) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to implement above approach
function findMax(arr, n, dp)
{
dp[0] = arr[0] ;
for(let i = 1 ; i <= n ; i++ )
{
let pick = arr[i];
if(i > 1)
{
pick += dp[i-2] ;
}
let notPick = 0 + dp[i-1] ;
dp[i] = Math.max(pick, notPick) ;
}
return dp[n];
}
// function to find the max value
function Func(nums)
{
if(nums.length == 1){
return nums[0] ;
}
// First and last element together
// can never be in the answer
let v1 = [], v2 = [];
let n = nums.length ;
// Store the maximum possible at each index
let dp = new Array(nums.length).fill(-1) ;
for(let i = 0 ; i <br n ; i++ ){
if(i != 0) v1.push(nums[i]) ;
if(i != n-1) v2.push(nums[i]) ;
}
// calculate the max when
// first element was considered
// and when last element was considered
document.write(Math.max(findMax(v1, n-2, dp) , findMax(v2, n-2, dp)),"</br>");
}
// Driver code
let arr = [ 1, 2, 3, 1 ];
Func(arr);
// This code is contributed by shinjanpatra
</script>
Complejidad de tiempo : O(N)
Complejidad del espacio auxiliar: O(N)
Artículo similar: suma máxima en una array circular tal que no hay dos elementos adyacentes