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)
{
Loot task = new Loot();
int []coins = { 7, 2, 6, 9, 1, 2, 5};
// Get number of element in given collection
int n = coins.length;
// Test
task.maximumLoot(coins, n);
}
}
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()
{
Loot *task = new Loot();
int coins[] = {
7 , 2 , 6 , 9 , 1 , 2 , 5
};
// Get number of element in given collection
int n = sizeof(coins) / sizeof(coins[0]);
// Test
task->maximumLoot(coins, n);
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)
{
Loot task = new Loot();
int[] coins = {
7 , 2 , 6 , 9 , 1 , 2 , 5
};
// Get number of element in given collection
int n = coins.Length;
// Test
task.maximumLoot(coins, n);
}
}
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()
{
$task = new Loot();
$coins = array(7, 2, 6, 9, 1, 2, 5);
// Get number of element in given collection
$n = count($coins);
// Test
$task->maximumLoot($coins, $n);
}
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 task = new Loot();
var coins = [7, 2, 6, 9, 1, 2, 5];
// Get number of element in given collection
var n = coins.length;
// Test
task.maximumLoot(coins, n);
}
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() :
task = Loot()
coins = [7, 2, 6, 9, 1, 2, 5]
# Get number of element in given collection
n = len(coins)
# Test
task.maximumLoot(coins, n)
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()
task = Loot.new()
coins = [7, 2, 6, 9, 1, 2, 5]
# Get number of element in given collection
n = coins.length
# Test
task.maximumLoot(coins, n)
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
task.maximumLoot(coins, n);
}
}
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 task: Loot = Loot();
let coins: [Int] = [7, 2, 6, 9, 1, 2, 5];
// Get number of element in given collection
let n: Int = coins.count;
// Test
task.maximumLoot(coins, n);
}
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 task: Loot = Loot();
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
task.maximumLoot(coins, n);
}
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.
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.
New Comment