Encuentre el máximo valor robado posible de las casas

Hay n casas construidas en una línea, cada una de las cuales contiene algún valor. Un ladrón va a robar el valor máximo de estas casas, pero no puede robar en dos casas contiguas porque el dueño de las casas robadas le dirá a sus dos vecinos del lado izquierdo y derecho. ¿Cuál es el valor máximo robado?

Ejemplos: 

Input: hval[] = {6, 7, 1, 3, 8, 2, 4}
Output: 19

Explanation: The thief will steal 6, 1, 8 and 4 from the house.

Input: hval[] = {5, 3, 4, 11, 2}
Output: 16

Explanation: Thief will steal 5 and 11

Enfoque ingenuo : dada una array, la solución es encontrar la subsecuencia de suma máxima donde no hay dos elementos seleccionados adyacentes. Entonces, el enfoque del problema es una solución recursiva. 

Así que hay dos casos:

1. Si se selecciona un elemento, no se puede seleccionar el siguiente elemento.
2. si no se selecciona un elemento, se puede seleccionar el siguiente elemento.

Implementación del enfoque recursivo:

// CPP program to find the maximum stolen value
#include <iostream>
using namespace std;
 
// calculate the maximum stolen value
int maxLoot(int* hval, int n)
{
    // base case
    if (n < 0) {
        return 0;
    }
 
    if (n == 0) {
        return hval[0];
    }
    // if current element is pick then previous cannot be
    // picked
    int pick = hval[n] + maxLoot(hval, n - 2);
    // if current element is not picked then previous
    // element is picked
    int notPick = maxLoot(hval, n - 1);
 
    // return max of picked and not picked
    return max(pick, notPick);
}
 
// Driver to test above code
int main()
{
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(hval) / sizeof(hval[0]);
    cout << "Maximum loot possible : "
         << maxLoot(hval, n - 1);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program to find the maximum stolen value
#include <stdio.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// calculate the maximum stolen value
int maxLoot(int* hval, int n)
{
    // base case
    if (n < 0)
        return 0;
 
    if (n == 0)
        return hval[0];
    // if current element is pick then previous cannot be
    // picked
    int pick = hval[n] + maxLoot(hval, n - 2);
    // if current element is not picked then previous
    // element is picked
    int notPick = maxLoot(hval, n - 1);
 
    // return max of picked and not picked
    return max(pick, notPick);
}
 
// Driver to test above code
int main()
{
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(hval) / sizeof(hval[0]);
    printf("Maximum loot possible : %d ",
           maxLoot(hval, n - 1));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

/*package whatever //do not write package name here */
// Java program to find the maximum stolen value
import java.io.*;
 
class GFG
{
   
  // Function to calculate the maximum stolen value
  static int maxLoot(int hval[], int n)
  {
     
    // base case
    if (n < 0) {
      return 0;
    }
 
    if (n == 0) {
      return hval[0];
    }
     
    // if current element is pick then previous cannot
    // be picked
    int pick = hval[n] + maxLoot(hval, n - 2);
     
    // if current element is not picked then previous
    // element is picked
    int notPick = maxLoot(hval, n - 1);
 
    // return max of picked and not picked
    return Math.max(pick, notPick);
  }
 
  // driver program
  public static void main(String[] args)
  {
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = hval.length;
    System.out.println("Maximum loot value : "
                       + maxLoot(hval, n-1));
  }
}
 
// This code is contributed by sanskar84.

# Python3 program to find the maximum stolen value
 
# calculate the maximum stolen value
def maxLoot(hval,n):
 
    # base case
    if (n < 0):
        return 0
 
    if (n == 0):
        return hval[0]
     
    # if current element is pick then previous cannot be
    # picked
    pick = hval[n] + maxLoot(hval, n - 2)
    # if current element is not picked then previous
    # element is picked
    notPick = maxLoot(hval, n - 1)
 
    # return max of picked and not picked
    return max(pick, notPick)
 
# Driver to test above code
hval = [ 6, 7, 1, 3, 8, 2, 4 ]
n = len(hval)
print("Maximum loot possible : ",maxLoot(hval, n - 1));
 
# This code is contributed by shinjanpatra

<script>
 
// JavaScript program to find the maximum stolen value
 
 
// calculate the maximum stolen value
function maxLoot(hval,n)
{
    // base case
    if (n < 0) {
        return 0;
    }
 
    if (n == 0) {
        return hval[0];
    }
    // if current element is pick then previous cannot be
    // picked
    let pick = hval[n] + maxLoot(hval, n - 2);
    // if current element is not picked then previous
    // element is picked
    let notPick = maxLoot(hval, n - 1);
 
    // return max of picked and not picked
    return Math.max(pick, notPick);
}
 
// Driver to test above code
 
let hval = [ 6, 7, 1, 3, 8, 2, 4 ];
let n = hval.length;
document.write("Maximum loot possible : ",maxLoot(hval, n - 1));
 
 
// This code is contributed by shinjanpatra
 
</script>

Maximum loot possible : 19

Análisis de Complejidad

Complejidad temporal:  O(2 ^N ) . Cada elemento tiene 2 opciones para escoger y no escoger
Complejidad espacial: O(2 ^N ). Se requiere un espacio de pila de recursión de tamaño 2 ⁿ , por lo que la complejidad del espacio es O(2 ^N ).

Método 2: Programación dinámica: enfoque de arriba hacia abajo

Entonces, la solución recursiva se puede idear fácilmente. Los subproblemas se pueden almacenar, reduciendo así la complejidad y convirtiendo la solución recursiva en un problema de programación dinámica.

Implementación:

// CPP program to find the maximum stolen value
#include <bits/stdc++.h>
using namespace std;
 
// calculate the maximum stolen value
int maxLoot(int *hval, int n, vector<int> &dp){
   
   // base case
   if(n < 0){
           return 0 ;
   }
    
   if(n == 0){
           return hval[0] ;
   }
   // If the subproblem is already solved
   // then return its value
   if(dp[n] != -1 ){
          return dp[n] ;
   }
   
   //if current element is pick then previous cannot be picked
   int pick = hval[n] +  maxLoot(hval, n-2, dp) ;
   //if current element is not picked then previous element is picked
   int notPick = maxLoot(hval, n-1, dp)  ;
   
   // return max of picked and not picked
   return dp[n] = max(pick, notPick) ;
   
}
 
// Driver to test above code
int main()
{
    int hval[] = {6, 7, 1, 3, 8, 2, 4};
    int n = sizeof(hval)/sizeof(hval[0]);
    // Initialize a dp vector
    vector<int> dp(n+1, -1) ;
    cout << "Maximum loot possible : "
        << maxLoot(hval, n-1, dp);
    return 0;
}

/*package whatever //do not write package name here */
 
// Java program to find the maximum stolen value
import java.io.*;
import java.util.Arrays;
 
class GFG {
  // Function to calculate the maximum stolen value
  static int maxLoot(int hval[], int n, int dp[])
  {
    // base case
    if (n < 0) {
      return 0;
    }
 
    if (n == 0) {
      return hval[0];
    }
    // If the subproblem is already solved
    // then return its value
    if (dp[n] != -1) {
      return dp[n];
    }
 
    // if current element is pick then previous cannot
    // be picked
    int pick = hval[n] + maxLoot(hval, n - 2, dp);
    // if current element is not picked then previous
    // element is picked
    int notPick = maxLoot(hval, n - 1, dp);
 
    // return max of picked and not picked
    return dp[n] = Math.max(pick, notPick);
  }
 
  // Driver program
  public static void main(String[] args)
  {
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = hval.length;
    int dp[] = new int[n + 1];
    Arrays.fill(dp, -1);
    System.out.println("Maximum loot value : "
                       + maxLoot(hval, n - 1, dp));
  }
}
 
// This code is contributed by sanskar84.

# Python3 program to find the maximum stolen value
 
# calculate the maximum stolen value
def maxLoot(hval,n,dp):
   
    # base case
    if(n < 0):
        return 0
    
    if(n == 0):
        return hval[0]
    
   # If the subproblem is already solved
   # then return its value
    if(dp[n] != -1):
        return dp[n]
 
   
    # if current element is pick then previous cannot be picked
    pick = hval[n] +  maxLoot(hval, n-2, dp)
     
    # if current element is not picked then previous element is picked
    notPick = maxLoot(hval, n-1, dp)
   
    # return max of picked and not picked
    dp[n] = max(pick, notPick)
    return dp[n]
   
# Driver to test above code
hval = [6, 7, 1, 3, 8, 2, 4]
n = len(hval)
 
# Initialize a dp vector
dp = [-1 for i in range(n+1)]
print("Maximum loot possible : "+str(maxLoot(hval, n-1, dp)))
 
# This code is contributed by shinjanpatra

<script>
 
// JavaScript program to find the maximum stolen value
 
// calculate the maximum stolen value
function maxLoot(hval,n,dp){
   
   // base case
   if(n < 0){
        return 0 ;
   }
    
   if(n == 0){
        return hval[0] ;
   }
   // If the subproblem is already solved
   // then return its value
   if(dp[n] != -1 ){
        return dp[n] ;
   }
   
   //if current element is pick then previous cannot be picked
   let pick = hval[n] +  maxLoot(hval, n-2, dp) ;
   //if current element is not picked then previous element is picked
   let notPick = maxLoot(hval, n-1, dp)  ;
   
   // return max of picked and not picked
   return dp[n] = Math.max(pick, notPick) ;
   
}
 
// Driver to test above code
let hval = [6, 7, 1, 3, 8, 2, 4];
let n = hval.length;
// Initialize a dp vector
let dp = new Array(n+1).fill(-1) ;
document.write("Maximum loot possible : ",maxLoot(hval, n-1, dp),"</br>");
// code is contributed by shinjanpatra
 
</script>

Maximum loot possible : 19

Análisis de Complejidad:  

Complejidad temporal: O(n) . Solo se necesita un recorrido de la array original. Entonces la complejidad del tiempo es O(n)
Complejidad del espacio:  O(n). Se requiere un espacio de pila recursivo de tamaño n, por lo que la complejidad del espacio es O(n).

Método 3: Programación dinámica: enfoque de abajo hacia arriba

Entonces, la solución recursiva se puede idear fácilmente. Los subproblemas se pueden almacenar, reduciendo así la complejidad y convirtiendo la solución recursiva en un problema de programación dinámica.

Algoritmo: 

1. Cree un espacio adicional dp , array DP para almacenar los subproblemas.
2. Aborde algunos casos básicos, si la longitud de la array es 0, imprima 0, si la longitud de la array es 1, imprima el primer elemento, si la longitud de la array es 2, imprima un máximo de dos elementos.
3. Actualice dp[0] como array[0] y dp[1] como máximo de array[0] y array[1]
4. Atraviese la array desde el segundo elemento (segundo índice) hasta el final de la array.
5. Para cada índice, actualice dp[i] como máximo de dp[i-2] + array[i] y dp[i-1] , este paso define los dos casos, si se selecciona un elemento, entonces no se puede seleccionar el elemento anterior y si no se selecciona un elemento, se puede seleccionar el elemento anterior.
6. Imprime el valor dp[n-1]

Implementación: 

// CPP program to find the maximum stolen value
#include <iostream>
using namespace std;
 
// calculate the maximum stolen value
int maxLoot(int* hval, int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return hval[0];
    if (n == 2)
        return max(hval[0], hval[1]);
 
    // dp[i] represent the maximum value stolen
    // so far after reaching house i.
    int dp[n];
 
    // Initialize the dp[0] and dp[1]
    dp[0] = hval[0];
    dp[1] = max(hval[0], hval[1]);
 
    // Fill remaining positions
    for (int i = 2; i < n; i++)
        dp[i] = max(hval[i] + dp[i - 2], dp[i - 1]);
 
    return dp[n - 1];
}
 
// Driver to test above code
int main()
{
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(hval) / sizeof(hval[0]);
    cout << "Maximum loot possible : " << maxLoot(hval, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program to find the maximum stolen value
#include <stdio.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// calculate the maximum stolen value
int maxLoot(int* hval, int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return hval[0];
    if (n == 2)
        return max(hval[0], hval[1]);
 
    // dp[i] represent the maximum value stolen
    // so far after reaching house i.
    int dp[n];
 
    // Initialize the dp[0] and dp[1]
    dp[0] = hval[0];
    dp[1] = max(hval[0], hval[1]);
 
    // Fill remaining positions
    for (int i = 2; i < n; i++)
        dp[i] = max(hval[i] + dp[i - 2], dp[i - 1]);
 
    return dp[n - 1];
}
 
// Driver to test above code
int main()
{
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(hval) / sizeof(hval[0]);
    printf("Maximum loot possible : %d", maxLoot(hval, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// Java program to find the maximum stolen value
import java.io.*;
 
class GFG {
    // Function to calculate the maximum stolen value
    static int maxLoot(int hval[], int n)
    {
        if (n == 0)
            return 0;
        if (n == 1)
            return hval[0];
        if (n == 2)
            return Math.max(hval[0], hval[1]);
 
        // dp[i] represent the maximum value stolen
        // so far after reaching house i.
        int[] dp = new int[n];
 
        // Initialize the dp[0] and dp[1]
        dp[0] = hval[0];
        dp[1] = Math.max(hval[0], hval[1]);
 
        // Fill remaining positions
        for (int i = 2; i < n; i++)
            dp[i]
                = Math.max(hval[i] + dp[i - 2], dp[i - 1]);
 
        return dp[n - 1];
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
        int n = hval.length;
        System.out.println("Maximum loot value : " + maxLoot(hval, n));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Python3 program to find the maximum stolen value
 
# calculate the maximum stolen value
def maximize_loot(hval, n):
    if n == 0:
        return 0
    if n == 1:
        return hval[0]
    if n == 2:
        return max(hval[0], hval[1])
 
    # dp[i] represent the maximum value stolen so
    # for after reaching house i.
    dp = [0]*n
 
    # Initialize the dp[0] and dp[1]
    dp[0] = hval[0]
    dp[1] = max(hval[0], hval[1])
     
    # Fill remaining positions
    for i in range(2, n):
        dp[i] = max(hval[i]+dp[i-2], dp[i-1])
 
    return dp[-1]
 
# Driver to test above code
def main():
 
    # Value of houses
    hval = [6, 7, 1, 3, 8, 2, 4]
 
    # number of houses
    n = len(hval)
    print("Maximum loot value : {}".
        format(maximize_loot(hval, n)))
 
if __name__ == '__main__':
    main()

// C# program to find the
// maximum stolen value
using System;
         
class GFG
{
   // Function to calculate the
   // maximum stolen value
    static int maxLoot(int []hval, int n)
    {
        if (n == 0)
        return 0;
        if (n == 1)
            return hval[0];
        if (n == 2)
            return Math.Max(hval[0], hval[1]);
 
        // dp[i] represent the maximum value stolen
        // so far after reaching house i.
        int[] dp = new int[n];
 
        // Initialize the dp[0] and dp[1]
        dp[0] = hval[0];
        dp[1] = Math.Max(hval[0], hval[1]);
 
        // Fill remaining positions
        for (int i = 2; i<n; i++)
            dp[i] = Math.Max(hval[i]+dp[i-2], dp[i-1]);
 
        return dp[n-1];
    }
     
    // Driver program
    public static void Main ()
    {
        int []hval = {6, 7, 1, 3, 8, 2, 4};
        int n = hval.Length;
        Console.WriteLine("Maximum loot value : " +
                                 maxLoot(hval, n));
    }
}
 
// This code is contributed by Sam007

<?php
// PHP program to find
// the maximum stolen value
 
// calculate the maximum
// stolen value
function maxLoot($hval, $n)
{
    if ($n == 0)
        return 0;
    if ($n == 1)
        return $hval[0];
    if ($n == 2)
        return max($hval[0],
                   $hval[1]);
 
    // dp[i] represent the maximum
    // value stolen so far after
    // reaching house i.
    $dp = array();
 
    // Initialize the
    // dp[0] and dp[1]
    $dp[0] = $hval[0];
    $dp[1] = max($hval[0],
                 $hval[1]);
 
    // Fill remaining positions
    for ($i = 2; $i < $n; $i++)
        $dp[$i] = max($hval[$i] +
                      $dp[$i - 2],
                      $dp[$i - 1]);
 
    return $dp[$n - 1];
}
 
// Driver Code
$hval = array(6, 7, 1,
              3, 8, 2, 4);
$n = sizeof($hval);
echo "Maximum loot possible : ",
             maxLoot($hval, $n);
     
// This code is contributed by aj_36
?>

<script>
 
    // Javascript program to find
    // the maximum stolen value
     
    // Function to calculate the
       // maximum stolen value
    function maxLoot(hval, n)
    {
        if (n == 0)
            return 0;
        if (n == 1)
            return hval[0];
        if (n == 2)
            return Math.max(hval[0], hval[1]);
   
        // dp[i] represent the maximum value stolen
        // so far after reaching house i.
        let dp = new Array(n);
   
        // Initialize the dp[0] and dp[1]
        dp[0] = hval[0];
        dp[1] = Math.max(hval[0], hval[1]);
   
        // Fill remaining positions
        for (let i = 2; i<n; i++)
            dp[i] = Math.max(hval[i]+dp[i-2], dp[i-1]);
   
        return dp[n-1];
    }
     
    let hval = [6, 7, 1, 3, 8, 2, 4];
    let n = hval.length;
    document.write(
    "Maximum loot value : " + maxLoot(hval, n)
    );
     
</script>

Maximum loot possible : 19

Análisis de Complejidad: 

• Tiempo Complejidad:  . 
  Solo se necesita un recorrido de la array original. Entonces la complejidad del tiempo es O(n)
• Complejidad espacial:  . 
  Se requiere una array de tamaño n, por lo que la complejidad del espacio es O(n).

Enfoque eficiente: al observar cuidadosamente la array DP, se puede ver que los valores de los dos índices anteriores son importantes al calcular el valor de un índice. Para reemplazar la array DP total por dos variables.

Algoritmo: 

1. Aborde algunos casos básicos, si la longitud de la array es 0, imprima 0, si la longitud de la array es 1, imprima el primer elemento, si la longitud de la array es 2, imprima un máximo de dos elementos.
2. Cree dos variables valor1 y valor2 valor1 como array[0] y valor2 como máximo de array[0] y array[1] y una variable max_val para almacenar la respuesta
3. Atraviese la array desde el segundo elemento (segundo índice) hasta el final de la array.
4. Para cada índice, actualice max_val como máximo de value1 + array[i] y value2 , este paso define los dos casos, si se selecciona un elemento, entonces no se puede seleccionar el elemento anterior y si no se selecciona un elemento, entonces se puede seleccionar el elemento anterior. seleccionado.
5. Para cada índice, actualice value1 = value2 y value2 = max_val
6. Imprime el valor de max_val

Implementación: 
 

// C++ program to find the maximum stolen value
#include <iostream>
using namespace std;
 
// calculate the maximum stolen value
int maxLoot(int* hval, int n)
{
    if (n == 0)
        return 0;
 
    int value1 = hval[0];
    if (n == 1)
        return value1;
 
    int value2 = max(hval[0], hval[1]);
    if (n == 2)
        return value2;
 
    // contains maximum stolen value at the end
    int max_val;
 
    // Fill remaining positions
    for (int i = 2; i < n; i++) {
        max_val = max(hval[i] + value1, value2);
        value1 = value2;
        value2 = max_val;
    }
 
    return max_val;
}
 
// Driver to test above code
int main()
{
    // Value of houses
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(hval) / sizeof(hval[0]);
    cout << "Maximum loot possible : " << maxLoot(hval, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program to find the maximum stolen value
#include <stdio.h>
 
//Find maximum between two numbers.
int max(int num1, int num2)
{
  return (num1 > num2) ? num1 : num2;
}
 
// calculate the maximum stolen value
int maxLoot(int* hval, int n)
{
    if (n == 0)
        return 0;
 
    int value1 = hval[0];
    if (n == 1)
        return value1;
 
    int value2 = max(hval[0], hval[1]);
    if (n == 2)
        return value2;
 
    // contains maximum stolen value at the end
    int max_val;
 
    // Fill remaining positions
    for (int i = 2; i < n; i++) {
        max_val = max(hval[i] + value1, value2);
        value1 = value2;
        value2 = max_val;
    }
 
    return max_val;
}
 
// Driver to test above code
int main()
{
    // Value of houses
    int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
    int n = sizeof(hval) / sizeof(hval[0]);
    printf("Maximum loot possible : %d", maxLoot(hval, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// Java program to find the maximum stolen value
import java.io.*;
 
class GFG {
    // Function to calculate the maximum stolen value
    static int maxLoot(int hval[], int n)
    {
        if (n == 0)
            return 0;
 
        int value1 = hval[0];
        if (n == 1)
            return value1;
 
        int value2 = Math.max(hval[0], hval[1]);
        if (n == 2)
            return value2;
 
        // contains maximum stolen value at the end
        int max_val = 0;
 
        // Fill remaining positions
        for (int i = 2; i < n; i++) {
            max_val = Math.max(hval[i] + value1, value2);
            value1 = value2;
            value2 = max_val;
        }
 
        return max_val;
    }
 
    // driver program
    public static void main(String[] args)
    {
        int hval[] = { 6, 7, 1, 3, 8, 2, 4 };
        int n = hval.length;
        System.out.println("Maximum loot value : "
                           + maxLoot(hval, n));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Python3 program to find the maximum stolen value
 
# calculate the maximum stolen value
def maximize_loot(hval, n):
    if n == 0:
        return 0
 
    value1 = hval[0]
    if n == 1:
        return value1
 
    value2 = max(hval[0], hval[1])
    if n == 2:
        return value2
 
    # contains maximum stolen value at the end
    max_val = None
 
    # Fill remaining positions
    for i in range(2, n):
        max_val = max(hval[i]+value1, value2)
        value1 = value2
        value2 = max_val
 
    return max_val
 
# Driver to test above code
def main():
 
    # Value of houses
    hval = [6, 7, 1, 3, 8, 2, 4]
 
    # number of houses
    n = len(hval)
    print("Maximum loot value : {}".format(maximize_loot(hval, n)))
 
if __name__ == '__main__':
    main()

// C# program to find the
// maximum stolen value
using System;
         
public class GFG
{
    // Function to calculate the
    // maximum stolen value
    static int maxLoot(int []hval, int n)
    {
        if (n == 0)
        return 0;
 
        int value1 = hval[0];
        if (n == 1)
            return value1;
 
        int value2 = Math.Max(hval[0], hval[1]);
        if (n == 2)
            return value2;
     
        // contains maximum stolen value at the end
        int max_val = 0;
 
        // Fill remaining positions
        for (int i = 2; i < n; i++)
        {
            max_val = Math.Max(hval[i] + value1, value2);
            value1 = value2;
            value2 = max_val;
        }
 
        return max_val;
    }
     
    // Driver program
    public static void Main ()
    {
        int []hval = {6, 7, 1, 3, 8, 2, 4};
        int n = hval.Length;
        Console.WriteLine("Maximum loot value : " +
                                 maxLoot(hval, n));
    }
}
 
// This code is contributed by Sam007

<?php
// PHP program to find
// the maximum stolen value
 
// calculate the
// maximum stolen value
function maxLoot($hval, $n)
{
    if ($n == 0)
        return 0;
 
    $value1 = $hval[0];
    if ($n == 1)
        return $value1;
 
    $value2 = max($hval[0],
                  $hval[1]);
    if ($n == 2)
        return $value2;
 
    // contains maximum
    // stolen value at the end
    $max_val;
 
    // Fill remaining positions
    for ($i = 2; $i < $n; $i++)
    {
        $max_val = max($hval[$i] +
                       $value1, $value2);
        $value1 = $value2;
        $value2 = $max_val;
    }
 
    return $max_val;
}
 
// Driver code
$hval = array(6, 7, 1, 3, 8, 2, 4);
$n = sizeof($hval);
echo "Maximum loot value : ",
          maxLoot($hval, $n);
     
// This code is contributed by ajit
?>

<script>
 
    // Javascript program to find the
    // maximum stolen value
     
    // Function to calculate the
    // maximum stolen value
    function maxLoot(hval, n)
    {
        if (n == 0)
            return 0;
  
        let value1 = hval[0];
        if (n == 1)
            return value1;
  
        let value2 = Math.max(hval[0], hval[1]);
        if (n == 2)
            return value2;
      
        // contains maximum stolen value at the end
        let max_val = 0;
  
        // Fill remaining positions
        for (let i = 2; i < n; i++)
        {
            max_val = Math.max(hval[i] +
                               value1, value2);
            value1 = value2;
            value2 = max_val;
        }
  
        return max_val;
    }
     
    let hval = [6, 7, 1, 3, 8, 2, 4];
    let n = hval.length;
    document.write("Maximum loot value : "
    + maxLoot(hval, n));
     
</script>

Maximum loot possible : 19

Análisis de Complejidad: 

• Complejidad de tiempo:  solo se necesita un recorrido de la array original. Entonces la complejidad del tiempo es O(n).
• Espacio Auxiliar:  No se requiere espacio extra por lo que la complejidad del espacio es constante.

Este artículo es una contribución de Atul Kumar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.