Suma máxima en una array circular tal que no hay dos elementos adyacentes

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *