# Find maximum possible stolen value from houses

In this article, we will discuss how to find the maximum possible stolen value from a row of houses. We'll explain the problem statement, provide a pseudocode algorithm with an explanation, and walk through the output of the provided Java code. The code uses dynamic programming to solve the problem efficiently.

## Problem Statement

You are a professional thief planning to rob houses along a street. Each house has a certain amount of money stashed, which is represented by an array of integers. However, adjacent houses have security systems connected, and if you rob two adjacent houses, an alarm will be triggered. Your task is to determine the maximum amount of money you can steal without triggering any alarms.

## Pseudocode Algorithm

Let's outline the algorithm to solve this problem:

```function maximumLoot(coins, n):
if n = 0:
result = 0
else if n = 1:
result = coins[0]
else if n = 2:
result = max(coins[0], coins[1])
else:
dp = new array of size n

dp[0] = coins[0]
dp[1] = max(coins[0], coins[1])

for i = 2 to n-1:
dp[i] = max(coins[i] + dp[i-2], dp[i-1])

result = dp[n-1]

printData(coins, n)
print("Result: " + result)

function printData(coins, n):
for i = 0 to n-1:
print(coins[i] + " ")

function max(a, b):
if a > b:
return a
else:
return b
```

The pseudocode above outlines the maximumLoot function which takes an array of coins and its size as input. It uses an auxiliary array, dp, to store the maximum stolen value up to each house. The function initializes dp[0] and dp[1] based on the values of coins[0] and coins[1]. It then iterates from i = 2 to n-1 and calculates dp[i] as the maximum of either stealing from the current house (coins[i] + dp[i-2]) or skipping the current house (dp[i-1]). Finally, it prints the input coins array and the calculated maximum stolen value.

## Code Solution

``````/*
Java Program for
Find maximum possible stolen value from houses
*/

public class Loot
{
public void printData(int []coins, int n)
{
for (int i = 0; i < n ; ++i )
{
System.out.print("  "+coins[i]);
}
}
// Returns the max value of given two values
public int maxValue(int a, int b)
{
if(a > b)
{
return a;
}
return b;
}
public void maximumLoot(int []coins, int n)
{
int result = -1;

if(n == 0)
{
result = 0;
}
else if(n == 1)
{
result = coins[0];
}
else if(n == 2)
{
result = maxValue(coins[0],coins[1]);
}
else
{
// Auxiliary variable
int []dp = new int[n];

// Set the first value
dp[0] = coins[0];

dp[1] = maxValue(coins[0], coins[1]);

// Calculated result
for (int i = 2; i < n; i++)
{
dp[i] = maxValue(coins[i]+dp[i-2], dp[i-1]);
}

result =  dp[n-1];
}

// Display given element
printData(coins, n);

// Display calculated result
System.out.println("\n Result  : "+result);

}
public static void main(String[] args)
{

int []coins = { 7, 2, 6, 9, 1, 2, 5};

// Get number of element in given collection
int n =  coins.length;

// Test

}
}``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find maximum possible stolen value from houses
*/
class Loot
{
public: void printData(int coins[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << "  " << coins[i];
}
}
// Returns the max value of given two values
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void maximumLoot(int coins[], int n)
{
int result = -1;
if (n == 0)
{
result = 0;
}
else if (n == 1)
{
result = coins[0];
}
else if (n == 2)
{
result = this->maxValue(coins[0], coins[1]);
}
else
{
// Auxiliary variable
int dp[n];
// Set the first value
dp[0] = coins[0];
dp[1] = this->maxValue(coins[0], coins[1]);
// Calculated result
for (int i = 2; i < n; i++)
{
dp[i] = this->maxValue(coins[i] + dp[i - 2], dp[i - 1]);
}
result = dp[n - 1];
}
// Display given element
this->printData(coins, n);
// Display calculated result
cout << "\n Result  : " << result << endl;
}
};
int main()
{
int coins[] = {
7 , 2 , 6 , 9 , 1 , 2 , 5
};
// Get number of element in given collection
int n = sizeof(coins) / sizeof(coins[0]);
// Test
return 0;
}``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````// Include namespace system
using System;
/*
Csharp Program for
Find maximum possible stolen value from houses
*/
public class Loot
{
public void printData(int[] coins, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write("  " + coins[i]);
}
}
// Returns the max value of given two values
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maximumLoot(int[] coins, int n)
{
int result = -1;
if (n == 0)
{
result = 0;
}
else if (n == 1)
{
result = coins[0];
}
else if (n == 2)
{
result = this.maxValue(coins[0], coins[1]);
}
else
{
// Auxiliary variable
int[] dp = new int[n];
// Set the first value
dp[0] = coins[0];
dp[1] = this.maxValue(coins[0], coins[1]);
// Calculated result
for (int i = 2; i < n; i++)
{
dp[i] = this.maxValue(coins[i] + dp[i - 2], dp[i - 1]);
}
result = dp[n - 1];
}
// Display given element
this.printData(coins, n);
// Display calculated result
Console.WriteLine("\n Result  : " + result);
}
public static void Main(String[] args)
{
int[] coins = {
7 , 2 , 6 , 9 , 1 , 2 , 5
};
// Get number of element in given collection
int n = coins.Length;
// Test
}
}``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````package main
import "fmt"
/*
Go Program for
Find maximum possible stolen value from houses
*/

func printData(coins[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print("  ", coins[i])
}
}
// Returns the max value of given two values
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func maximumLoot(coins[] int, n int) {
var result int = -1
if n == 0 {
result = 0
} else if n == 1 {
result = coins[0]
} else if n == 2 {
result = maxValue(coins[0], coins[1])
} else {
// Auxiliary variable
var dp = make([] int, n)
// Set the first value
dp[0] = coins[0]
dp[1] = maxValue(coins[0], coins[1])
// Calculated result
for i := 2 ; i < n ; i++ {
dp[i] = maxValue(coins[i] + dp[i - 2], dp[i - 1])
}
result = dp[n - 1]
}
// Display given element
printData(coins, n)
// Display calculated result
fmt.Println("\n Result  : ", result)
}
func main() {

var coins = [] int {7, 2, 6, 9, 1, 2, 5}
// Get number of element in given collection
var n int = len(coins)
// Test
maximumLoot(coins, n)
}``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````<?php
/*
Php Program for
Find maximum possible stolen value from houses
*/
class Loot
{
public	function printData(\$coins, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo("  ".\$coins[\$i]);
}
}
// Returns the max value of given two values
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function maximumLoot(\$coins, \$n)
{
\$result = -1;
if (\$n == 0)
{
\$result = 0;
}
else if (\$n == 1)
{
\$result = \$coins[0];
}
else if (\$n == 2)
{
\$result = \$this->maxValue(\$coins[0], \$coins[1]);
}
else
{
// Auxiliary variable
\$dp = array_fill(0, \$n, 0);
// Set the first value
\$dp[0] = \$coins[0];
\$dp[1] = \$this->maxValue(\$coins[0], \$coins[1]);
// Calculated result
for (\$i = 2; \$i < \$n; \$i++)
{
\$dp[\$i] = \$this->maxValue(
\$coins[\$i] + \$dp[\$i - 2], \$dp[\$i - 1]
);
}
\$result = \$dp[\$n - 1];
}
// Display given element
\$this->printData(\$coins, \$n);
// Display calculated result
echo("\n Result  : ".\$result."\n");
}
}

function main()
{
\$coins = array(7, 2, 6, 9, 1, 2, 5);
// Get number of element in given collection
\$n = count(\$coins);
// Test
}
main();``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````/*
Node JS Program for
Find maximum possible stolen value from houses
*/
class Loot
{
printData(coins, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write("  " + coins[i]);
}
}
// Returns the max value of given two values
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
maximumLoot(coins, n)
{
var result = -1;
if (n == 0)
{
result = 0;
}
else if (n == 1)
{
result = coins[0];
}
else if (n == 2)
{
result = this.maxValue(coins[0], coins[1]);
}
else
{
// Auxiliary variable
var dp = Array(n).fill(0);
// Set the first value
dp[0] = coins[0];
dp[1] = this.maxValue(coins[0], coins[1]);
// Calculated result
for (var i = 2; i < n; i++)
{
dp[i] = this.maxValue(
coins[i] + dp[i - 2], dp[i - 1]
);
}
result = dp[n - 1];
}
// Display given element
this.printData(coins, n);
// Display calculated result
console.log("\n Result  : " + result);
}
}

function main()
{
var coins = [7, 2, 6, 9, 1, 2, 5];
// Get number of element in given collection
var n = coins.length;
// Test
}
main();``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````#    Python 3 Program for
#    Find maximum possible stolen value from houses
class Loot :
def printData(self, coins, n) :
i = 0
while (i < n) :
print("  ", coins[i], end = "")
i += 1

#  Returns the max value of given two values
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def maximumLoot(self, coins, n) :
result = -1
if (n == 0) :
result = 0
elif (n == 1) :
result = coins[0]
elif (n == 2) :
result = self.maxValue(coins[0], coins[1])
else :
#  Auxiliary variable
dp = [0] * (n)
#  Set the first value
dp[0] = coins[0]
dp[1] = self.maxValue(coins[0], coins[1])
i = 2
#  Calculated result
while (i < n) :
dp[i] = self.maxValue(coins[i] + dp[i - 2], dp[i - 1])
i += 1

result = dp[n - 1]

#  Display given element
self.printData(coins, n)
#  Display calculated result
print("\n Result  : ", result)

def main() :
coins = [7, 2, 6, 9, 1, 2, 5]
#  Get number of element in given collection
n = len(coins)
#  Test

if __name__ == "__main__": main()``````

#### Output

``````   7   2   6   9   1   2   5
Result  :  21``````
``````#    Ruby Program for
#    Find maximum possible stolen value from houses
class Loot
def printData(coins, n)
i = 0
while (i < n)
print("  ", coins[i])
i += 1
end

end

#  Returns the max value of given two values
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def maximumLoot(coins, n)
result = -1
if (n == 0)
result = 0
elsif (n == 1)
result = coins[0]
elsif (n == 2)
result = self.maxValue(coins[0], coins[1])
else

#  Auxiliary variable
dp = Array.new(n) {0}
#  Set the first value
dp[0] = coins[0]
dp[1] = self.maxValue(coins[0], coins[1])
i = 2
#  Calculated result
while (i < n)
dp[i] = self.maxValue(coins[i] + dp[i - 2], dp[i - 1])
i += 1
end

result = dp[n - 1]
end

#  Display given element
self.printData(coins, n)
#  Display calculated result
print("\n Result  : ", result, "\n")
end

end

def main()
coins = [7, 2, 6, 9, 1, 2, 5]
#  Get number of element in given collection
n = coins.length
#  Test
end

main()``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21
``````
``````/*
Scala Program for
Find maximum possible stolen value from houses
*/
class Loot()
{
def printData(coins: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print("  " + coins(i));
i += 1;
}
}
// Returns the max value of given two values
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def maximumLoot(coins: Array[Int], n: Int): Unit = {
var result: Int = -1;
if (n == 0)
{
result = 0;
}
else if (n == 1)
{
result = coins(0);
}
else if (n == 2)
{
result = maxValue(coins(0), coins(1));
}
else
{
// Auxiliary variable
var dp: Array[Int] = Array.fill[Int](n)(0);
// Set the first value
dp(0) = coins(0);
dp(1) = maxValue(coins(0), coins(1));
var i: Int = 2;
// Calculated result
while (i < n)
{
dp(i) = maxValue(coins(i) + dp(i - 2), dp(i - 1));
i += 1;
}
result = dp(n - 1);
}
// Display given element
printData(coins, n);
// Display calculated result
println("\n Result  : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Loot = new Loot();
var coins: Array[Int] = Array(7, 2, 6, 9, 1, 2, 5);
// Get number of element in given collection
var n: Int = coins.length;
// Test
}
}``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````
``````import Foundation;
/*
Swift 4 Program for
Find maximum possible stolen value from houses
*/
class Loot
{
func printData(_ coins: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print("  ", coins[i], terminator: "");
i += 1;
}
}
// Returns the max value of given two values
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func maximumLoot(_ coins: [Int], _ n: Int)
{
var result: Int = -1;
if (n == 0)
{
result = 0;
}
else if (n == 1)
{
result = coins[0];
}
else if (n == 2)
{
result = self.maxValue(coins[0], coins[1]);
}
else
{
// Auxiliary variable
var dp: [Int] = Array(repeating: 0, count: n);
// Set the first value
dp[0] = coins[0];
dp[1] = self.maxValue(coins[0], coins[1]);
var i: Int = 2;
// Calculated result
while (i < n)
{
dp[i] = self.maxValue(coins[i] + dp[i - 2], dp[i - 1]);
i += 1;
}
result = dp[n - 1];
}
// Display given element
self.printData(coins, n);
// Display calculated result
print("\n Result  : ", result);
}
}
func main()
{
let coins: [Int] = [7, 2, 6, 9, 1, 2, 5];
// Get number of element in given collection
let n: Int = coins.count;
// Test
}
main();``````

#### Output

``````   7   2   6   9   1   2   5
Result  :  21``````
``````/*
Kotlin Program for
Find maximum possible stolen value from houses
*/
class Loot
{
fun printData(coins: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print("  " + coins[i]);
i += 1;
}
}
// Returns the max value of given two values
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun maximumLoot(coins: Array < Int > , n: Int): Unit
{
var result: Int ;
if (n == 0)
{
result = 0;
}
else if (n == 1)
{
result = coins[0];
}
else if (n == 2)
{
result = this.maxValue(coins[0], coins[1]);
}
else
{
// Auxiliary variable
val dp: Array < Int > = Array(n)
{
0
};
// Set the first value
dp[0] = coins[0];
dp[1] = this.maxValue(coins[0], coins[1]);
var i: Int = 2;
// Calculated result
while (i < n)
{
dp[i] = this.maxValue(coins[i] + dp[i - 2], dp[i - 1]);
i += 1;
}
result = dp[n - 1];
}
// Display given element
this.printData(coins, n);
// Display calculated result
println("\n Result  : " + result);
}
}
fun main(args: Array < String > ): Unit
{
val coins: Array < Int > = arrayOf(7, 2, 6, 9, 1, 2, 5);
// Get number of element in given collection
val n: Int = coins.count();
// Test
}``````

#### Output

``````  7  2  6  9  1  2  5
Result  : 21``````

## Output Explanation

The provided Java code uses the maximumLoot function to solve the problem for a given array of coins [7, 2, 6, 9, 1, 2, 5]. The expected output is:

```7 2 6 9 1 2 5
Result: 21
```

The output is displayed in two lines. The first line represents the input coins array, and the second line shows the calculated maximum stolen value, which is 21 in this case.

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of houses. This is because we iterate through the houses once to calculate the maximum stolen value using dynamic programming. The space complexity is also O(n) as we use an auxiliary array, dp, of size n to store intermediate results.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.