Skip to main content

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.

Last updated on by Kalkicode




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.

New Comment