Dada una array circular que contiene valores enteros positivos. La tarea es encontrar la suma máxima de una subsecuencia con la restricción de que no debe haber 2 números en la secuencia adyacentes en la array.
Ejemplos:
Input: circular arr = {1, 2, 3, 1}
Output : 4
subsequence will be(1, 3), hence 1 + 3 = 4
Input: circular arr = {1, 2, 3, 4, 5, 1}
Output: 9
subsequence will be(1, 3, 5), hence 1 + 3 + 5 = 9
Enfoque ingenuo: este problema es una extensión del problema https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/. En este problema, los elementos arr están dispuestos de forma circular, de modo que el primero y el último elemento también son adyacentes. Por lo tanto, no podemos tomar el primer y el último elemento juntos, por lo que podemos tomar el elemento 1 o el último elemento. Entonces, primero podemos tomar el elemento 1 y excluir el último elemento y calcular la subsecuencia de suma máxima donde no hay dos elementos seleccionados adyacentes y luego también podemos calcular otra respuesta excluyendo el primer elemento e incluyendo el último elemento. Y tomaremos máximo dos.
Implementación del enfoque recursivo:
C++
// CPP program to find maximum sum in a circular array
// such that no elements are adjacent in the sum.
#include<iostream>
using namespace std;
// calculate the maximum stolen value
int helper(int* arr, int n)
{
// base case
if (n < 0) {
return 0;
}
if (n == 0) {
return arr[0];
}
// if current element is pick then previous cannot be
// picked
int pick = arr[n] + helper(arr, n - 2);
// if current element is not picked then previous
// element is picked
int notPick = helper(arr, n - 1);
// return max of picked and not picked
return max(pick, notPick);
}
int maxLoot(int* arr, int n)
{
// case 1: Last element is exluded we have to calculate
// result for first n-1 houses.
int ans1 = helper(arr, n - 1);
// case 2: First element is excluded we have to
// calculate result 2 to n houses.
int ans2 = helper(arr + 1, n - 1);
return max(ans1, ans2);
}
// Driver to test above code
int main()
{
int arr[] = { 1, 2, 3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum loot possible : "
<< maxLoot(arr, n - 1);
return 0;
}
// This code is contributed by Sanskar Bharadia
Producción
Maximum loot possible : 4
Análisis de Complejidad:
Complejidad temporal: O(2 n ).
Espacio Auxiliar: O(N)
Enfoque El problema se puede resolver usando DP. Ya se ha discutido un enfoque en esta publicación, pero es para una array. Podemos tratar el subarreglo circular como dos arrays, uno desde (0 a n-2-avo) y (1 a n-1-avo) índice, y usar el enfoque utilizado en la publicación anterior . La suma máxima devuelta por ambos será la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find maximum sum in a circular array
// such that no elements are adjacent in the sum.
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum
// from 0th position to(n-2)th position
int maxSum1(int arr[], int n)
{
int dp[n];
int maxi = 0;
for (int i = 0; i < n - 1; i++) {
// copy the element of original array to dp[]
dp[i] = arr[i];
// find the maximum element in the array
if (maxi < arr[i])
maxi = arr[i];
}
// start from 2nd to n-1th pos
for (int i = 2; i < n - 1; i++) {
// traverse for all pairs
// bottom-up approach
for (int j = 0; j < i - 1; j++) {
// dp-condition
if (dp[i] < dp[j] + arr[i]) {
dp[i] = dp[j] + arr[i];
// find maximum sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return the maximum
return maxi;
}
// Function to find the maximum sum
// from 1st position to n-1-th position
int maxSum2(int arr[], int n)
{
int dp[n];
int maxi = 0;
for (int i = 1; i < n; i++) {
dp[i] = arr[i];
if (maxi < arr[i])
maxi = arr[i];
}
// Traverse from third to n-th pos
for (int i = 3; i < n; i++) {
// bottom-up approach
for (int j = 1; j < i - 1; j++) {
// dp condition
if (dp[i] < arr[i] + dp[j]) {
dp[i] = arr[i] + dp[j];
// find max sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return max
return maxi;
}
int findMaxSum(int arr[], int n)
{
return max(maxSum1(arr, n), maxSum2(arr, n));
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 1 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << findMaxSum(arr, n);
return 0;
}
Java
// Java program to find maximum sum in a circular array
// such that no elements are adjacent in the sum.
import java.io.*;
class GFG {
// Function to calculate the sum
// from 0th position to(n-2)th position
static int maxSum1(int arr[], int n)
{
int dp[]=new int[n];
int maxi = 0;
for (int i = 0; i < n - 1; i++) {
// copy the element of original array to dp[]
dp[i] = arr[i];
// find the maximum element in the array
if (maxi < arr[i])
maxi = arr[i];
}
// start from 2nd to n-1th pos
for (int i = 2; i < n - 1; i++) {
// traverse for all pairs
// bottom-up approach
for (int j = 0; j < i - 1; j++) {
// dp-condition
if (dp[i] < dp[j] + arr[i]) {
dp[i] = dp[j] + arr[i];
// find maximum sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return the maximum
return maxi;
}
// Function to find the maximum sum
// from 1st position to n-1-th position
static int maxSum2(int arr[], int n)
{
int dp[]=new int[n];
int maxi = 0;
for (int i = 1; i < n; i++) {
dp[i] = arr[i];
if (maxi < arr[i])
maxi = arr[i];
}
// Traverse from third to n-th pos
for (int i = 3; i < n; i++) {
// bottom-up approach
for (int j = 1; j < i - 1; j++) {
// dp condition
if (dp[i] < arr[i] + dp[j]) {
dp[i] = arr[i] + dp[j];
// find max sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return max
return maxi;
}
static int findMaxSum(int arr[], int n)
{
int t=Math.max(maxSum1(arr, n), maxSum2(arr, n));
return t;
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 1, 2, 3, 1 };
int n = arr.length;
System.out.println(findMaxSum(arr, n));
}
}
Python 3
# Python 3 program to find maximum sum # in a circular array such that no # elements are adjacent in the sum. # Function to calculate the sum from # 0th position to(n-2)th position def maxSum1(arr, n): dp = [0] * n maxi = 0 for i in range(n - 1): # copy the element of original # array to dp[] dp[i] = arr[i] # find the maximum element in the array if (maxi < arr[i]): maxi = arr[i] # start from 2nd to n-1th pos for i in range(2, n - 1): # traverse for all pairs bottom-up # approach for j in range(i - 1) : # dp-condition if (dp[i] < dp[j] + arr[i]): dp[i] = dp[j] + arr[i] # find maximum sum if (maxi < dp[i]): maxi = dp[i] # return the maximum return maxi # Function to find the maximum sum # from 1st position to n-1-th position def maxSum2(arr, n): dp = [0] * n maxi = 0 for i in range(1, n): dp[i] = arr[i] if (maxi < arr[i]): maxi = arr[i] # Traverse from third to n-th pos for i in range(3, n): # bottom-up approach for j in range(1, i - 1) : # dp condition if (dp[i] < arr[i] + dp[j]): dp[i] = arr[i] + dp[j] # find max sum if (maxi < dp[i]): maxi = dp[i] # return max return maxi def findMaxSum(arr, n): return max(maxSum1(arr, n), maxSum2(arr, n)) # Driver Code if __name__ == "__main__": arr = [ 1, 2, 3, 1 ] n = len(arr) print(findMaxSum(arr, n)) # This code is contributed by ita_c
C#
// C# program to find maximum sum
// in a circular array such that
// no elements are adjacent in the sum.
using System;
class GFG
{
// Function to calculate the sum
// from 0th position to(n-2)th position
static int maxSum1(int []arr, int n)
{
int []dp = new int[n];
int maxi = 0;
for (int i = 0; i < n - 1; i++)
{
// copy the element of original
// array to dp[]
dp[i] = arr[i];
// find the maximum element
// in the array
if (maxi < arr[i])
maxi = arr[i];
}
// start from 2nd to n-1th pos
for (int i = 2; i < n - 1; i++)
{
// traverse for all pairs
// bottom-up approach
for (int j = 0; j < i - 1; j++)
{
// dp-condition
if (dp[i] < dp[j] + arr[i])
{
dp[i] = dp[j] + arr[i];
// find maximum sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return the maximum
return maxi;
}
// Function to find the maximum sum
// from 1st position to n-1-th position
static int maxSum2(int []arr, int n)
{
int []dp = new int[n];
int maxi = 0;
for (int i = 1; i < n; i++)
{
dp[i] = arr[i];
if (maxi < arr[i])
maxi = arr[i];
}
// Traverse from third to n-th pos
for (int i = 3; i < n; i++)
{
// bottom-up approach
for (int j = 1; j < i - 1; j++)
{
// dp condition
if (dp[i] < arr[i] + dp[j])
{
dp[i] = arr[i] + dp[j];
// find max sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return max
return maxi;
}
static int findMaxSum(int []arr, int n)
{
int t = Math.Max(maxSum1(arr, n),
maxSum2(arr, n));
return t;
}
// Driver Code
static public void Main ()
{
int []arr = { 1, 2, 3, 1 };
int n = arr.Length;
Console.WriteLine(findMaxSum(arr, n));
}
}
// This code is contributed
// by Sach_Code
PHP
<?php
// PHP program to find maximum sum in
// a circular array such that no
// elements are adjacent in the sum.
// Function to calculate the sum
// from 0th position to(n-2)th position
function maxSum1($arr, $n)
{
$dp[$n] = array();
$maxi = 0;
for ($i = 0; $i < $n - 1; $i++)
{
// copy the element of original
// array to dp[]
$dp[$i] = $arr[$i];
// find the maximum element in the array
if ($maxi < $arr[$i])
$maxi = $arr[$i];
}
// start from 2nd to n-1th pos
for ($i = 2; $i < $n - 1; $i++)
{
// traverse for all pairs
// bottom-up approach
for ( $j = 0; $j < $i - 1; $j++)
{
// dp-condition
if ($dp[$i] < $dp[$j] + $arr[$i])
{
$dp[$i] = $dp[$j] + $arr[$i];
// find maximum sum
if ($maxi < $dp[$i])
$maxi = $dp[$i];
}
}
}
// return the maximum
return $maxi;
}
// Function to find the maximum sum
// from 1st position to n-1-th position
function maxSum2($arr, $n)
{
$dp[$n] = array();
$maxi = 0;
for ($i = 1; $i < $n; $i++)
{
$dp[$i] = $arr[$i];
if ($maxi < $arr[$i])
$maxi = $arr[$i];
}
// Traverse from third to n-th pos
for ($i = 3; $i < $n; $i++)
{
// bottom-up approach
for ($j = 1; $j < $i - 1; $j++)
{
// dp condition
if ($dp[$i] < $arr[$i] + $dp[$j])
{
$dp[$i] = $arr[$i] + $dp[$j];
// find max sum
if ($maxi < $dp[$i])
$maxi = $dp[$i];
}
}
}
// return max
return $maxi;
}
function findMaxSum($arr, $n)
{
return max(maxSum1($arr, $n),
maxSum2($arr, $n));
}
// Driver Code
$arr = array(1, 2, 3, 1 );
$n = sizeof($arr);
echo findMaxSum($arr, $n);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// JavaScript program to find maximum sum
// in a circular array such that
// no elements are adjacent in the sum.
// Function to calculate the sum
// from 0th position to(n-2)th position
function maxSum1(arr, n)
{
let dp = new Array(n);
let maxi = 0;
for (i = 0; i < n - 1; i++)
{
// copy the element of original
// array to dp[]
dp[i] = arr[i];
// find the maximum element
// in the array
if (maxi < arr[i])
maxi = arr[i];
}
// start from 2nd to n-1th pos
for (i = 2; i < n - 1; i++)
{
// traverse for all pairs
// bottom-up approach
for (j = 0; j < i - 1; j++)
{
// dp-condition
if (dp[i] < dp[j] + arr[i])
{
dp[i] = dp[j] + arr[i];
// find maximum sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return the maximum
return maxi;
}
// Function to find the maximum sum
// from 1st position to n-1-th position
function maxSum2(arr, n)
{
let dp = new Array(n);
let maxi = 0;
for (i = 1; i < n; i++)
{
dp[i] = arr[i];
if (maxi < arr[i])
maxi = arr[i];
}
// Traverse from third to n-th pos
for (i = 3; i < n; i++)
{
// bottom-up approach
for (j = 1; j < i - 1; j++)
{
// dp condition
if (dp[i] < arr[i] + dp[j])
{
dp[i] = arr[i] + dp[j];
// find max sum
if (maxi < dp[i])
maxi = dp[i];
}
}
}
// return max
return maxi;
}
function findMaxSum(arr, n)
{
let t = Math.max(maxSum1(arr, n),
maxSum2(arr, n));
return t;
}
// Driver Code
let arr = [1, 2, 3, 1 ];
let n = arr.length;
document.write(findMaxSum(arr, n));
// This code is contributed by mohit kumar 29.
</script>
Producción
4
Complejidad del tiempo: O(N^2)
Enfoque de optimización del espacio: como podemos ver, el dp[i] se calcula a partir de valores anteriores, por lo que podemos almacenar esos valores anteriores en variables.
C++
// C++ program to find the maximum stolen value
#include <iostream>
using namespace std;
// calculate the maximum stolen value
int findMaxSum(int arr[], int n)
{
if (n == 0)
return 0;
int value1 = arr[0];
if (n == 1)
return value1;
int value2 = 0;
// case 1: check for 1 to n-1 houses.
// contains maximum stolen value at the end
int max_val1, max_val2;
// Fill remaining positions
for (int i = 1; i < n - 1; i++) {
int first = value1;
int second = arr[i];
if (i > 1) {
second += value2;
}
int curr = max(first, second);
value2 = value1;
value1 = curr;
}
// case 2: check for 2 to n houses.
max_val1 = value1;
value1 = arr[1];
value2 = 0;
for (int i = 2; i < n; i++) {
int first = value1;
int second = arr[i];
if (i > 1) {
second += value2;
}
int curr = max(first, second);
value2 = value1;
value1 = curr;
}
max_val2 = value1;
return max(max_val1, max_val2);
}
// Driver to test above code
int main()
{
// Value of houses
int arr[] = { 6, 7, 1, 3, 8, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaxSum(arr, n);
return 0;
}
Java
// Java program to find the maximum stolen value
public class GFG {
// calculate the maximum stolen value
static int findMaxSum(int[] arr, int n)
{
if (n == 0)
return 0;
int value1 = arr[0];
if (n == 1)
return value1;
int value2 = 0;
// case 1: check for 1 to n-1 houses.
// contains maximum stolen value at the end
int max_val1, max_val2;
// Fill remaining positions
for (int i = 1; i < n - 1; i++) {
int first = value1;
int second = arr[i];
if (i > 1) {
second += value2;
}
int curr = Math.max(first, second);
value2 = value1;
value1 = curr;
}
// case 2: check for 2 to n houses.
max_val1 = value1;
value1 = arr[1];
value2 = 0;
for (int i = 2; i < n; i++) {
int first = value1;
int second = arr[i];
if (i > 1) {
second += value2;
}
int curr = Math.max(first, second);
value2 = value1;
value1 = curr;
}
max_val2 = value1;
return Math.max(max_val1, max_val2);
}
// Driver Code
public static void main (String[] args)
{
// Value of houses
int arr[] = { 6, 7, 1, 3, 8, 2, 4 };
int n = arr.length;
System.out.println(findMaxSum(arr, n));
}
}
// This code is contributed by aditya942003patil
Producción
19
Análisis de Complejidad:
Complejidad temporal: O(N).
Complejidad espacial: O(1).
Publicación traducida automáticamente
Artículo escrito por Mohd_Saliem y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA