Find the maximum possible stolen value from houses using O(n) extra space
Here, we are finding which will be the best pattern to steal a house without getting any police alert
the approach has one edge case there will be only one/two houses then the output will be
maximum money that is there in any house
else will be traverse for all houses and try to find the maximum amount that can get by coming from the previous house to current house
and at the end, we will just output maximum amount along the vector.
C++
#include <bits/stdc++.h> #include <iostream> #define int long long using namespace std; void solve( int n, vector< int >& v) { vector< int > dp(n, -2); int maxmoney = 0; if (n == 1 || n == 2) { cout << "Maximum loot possible : " ; cout << *max_element(v.begin(), v.end()) << endl; return ; } dp[0] = v[0]; dp[1] = v[1]; for ( int i = 2; i < n; i++) { int money = 0; dp[i] = v[i]; for ( int j = i - 2; j >= 0; j--) { money = max(money, dp[j]); } dp[i] += money; } int m = *max_element(dp.begin(), dp.end()); cout << "Maximum loot possible : " ; cout << m << endl; return ; } signed main() { // int t;cin>>t; // while(t--){ int n = 7; vector< int > v{ 6, 7, 1, 3, 8, 2, 4 }; solve(n, v); //} return 0; } |
Java
// Java code for the above approach import java.util.Arrays; import java.util.Scanner; public class Main { public static void solve( int n, int [] v) { int [] dp = new int [n]; Arrays.fill(dp, - 2 ); int maxmoney = 0 ; if (n == 1 || n == 2 ) { System.out.print( "Maximum loot possible : " ); int max = Integer.MIN_VALUE; for ( int i = 0 ; i < v.length; i++) { max = Math.max(v[i], max); } System.out.println(max); return ; } dp[ 0 ] = v[ 0 ]; dp[ 1 ] = v[ 1 ]; for ( int i = 2 ; i < n; i++) { int money = 0 ; dp[i] = v[i]; for ( int j = i - 2 ; j >= 0 ; j--) { money = Math.max(money, dp[j]); } dp[i] += money; } int m = Arrays.stream(dp).max().getAsInt(); System.out.print( "Maximum loot possible : " ); System.out.println(m); return ; } public static void main(String[] args) { int n = 7 ; int [] v = { 6 , 7 , 1 , 3 , 8 , 2 , 4 }; solve(n, v); } } // This code is contributed by lokeshpotta20. |
Python3
def solve(n, v): dp = [ - 2 ] * (n) maxmoney = 0 if (n = = 1 or n = = 2 ): print ( "Maximum loot possible : " ) print ( max (v)) return dp[ 0 ] = v[ 0 ] dp[ 1 ] = v[ 1 ] for i in range ( 2 ,n): money = 0 dp[i] = v[i] for j in range (i - 2 , - 1 , - 1 ): money = max (money, dp[j]) dp[i] + = money m = max (dp) print ( "Maximum loot possible :" , m) return n = 7 v = [ 6 , 7 , 1 , 3 , 8 , 2 , 4 ] solve(n, v) |
Javascript
function solve(n, v) { let dp= new Array(n).fill(-2); let maxmoney = 0; if (n == 1 || n == 2) { document.write( "Maximum loot possible : " ); console.write(Math.max(...v)); return ; } dp[0] = v[0]; dp[1] = v[1]; for (let i = 2; i < n; i++) { let money = 0; dp[i] = v[i]; for (let j = i - 2; j >= 0; j--) { money = Math.max(money, dp[j]); } dp[i] += money; } let m = Math.max(...dp); document.write( "Maximum loot possible : " ); document.write(m); return ; } // int t;cin>>t; // while(t--){ let n = 7; let v = [6, 7, 1, 3, 8, 2, 4 ]; solve(n, v); //} |
C#
// C# Program to implement the above approach using System; using System.Linq; using System.Collections.Generic; class GFG { static void solve( int n, List< int > v) { List< int > dp= new List< int >(); for ( int i=0; i<n; i++) dp.Add(-2); int maxmoney = 0; if (n == 1 || n == 2) { Console.Write( "Maximum loot possible : " ); Console.Write(v.Max()+ "\n" ); return ; } dp[0] = v[0]; dp[1] = v[1]; for ( int i = 2; i < n; i++) { int money = 0; dp[i] = v[i]; for ( int j = i - 2; j >= 0; j--) { money = Math.Max(money, dp[j]); } dp[i] += money; } int m = dp.Max(); Console.Write( "Maximum loot possible : " ); Console.Write(m); return ; } static public void Main() { // int t;cin>>t; // while(t--){ int n = 7; List< int > v= new List< int >{ 6, 7, 1, 3, 8, 2, 4 }; solve(n, v); //} } } |
Maximum loot possible : 19
Time Complexity: O(n^2). for the worst case for the last element it will traverse over all elements of the vector.
Space Complexity: O(n). the only used space is dp vector of o(n).
Find maximum possible stolen value from houses (House Robber)
There are N houses built in a line, each of which contains some value in it. A thief is going to steal the maximum value of these houses, but he can’t steal in two adjacent houses because the owner of the stolen houses will tell his two neighbors left and right sides. The task is to find what is the maximum stolen value.
Examples:
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
Naive Approach: Below is the idea to solve the problem:
Given an array, the solution is to find the maximum sum subsequence where no two selected elements are adjacent. So the approach to the problem is a recursive solution.
So there are two cases:
- If an element is selected then the next element cannot be selected.
- if an element is not selected then the next element can be selected.
Use recursion to find the result for both cases.
Below is the Implementation of the above approach:
C++
// 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
// 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) |
Java
/*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 possible : " + maxLoot(hval, n- 1 )); } } // This code is contributed by sanskar84. |
Python3
# 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 |
C#
// 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) { // 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); } static public void Main() { // Code int [] hval = { 6, 7, 1, 3, 8, 2, 4 }; int n = hval.Length; Console.WriteLine( "Maximum loot possible : " + maxLoot(hval, n - 1)); } } // This code is contributed by lokesmvs21. |
Javascript
<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
Time Complexity: O(2N). Every element has 2 choices to pick and not pick
Auxiliary Space: O(2N). A recursion stack space is required of size 2n, so space complexity is O(2N).