Find maximum possible stolen value from houses using constant Space
By carefully observing the DP array, it can be seen that the values of the previous two indices matter while calculating the value for an index. To replace the total DP array with two variables.
Follow the below steps to Implement the idea:
- Tackle some basic cases, if the length of the array is 0, print 0, if the length of the array is 1, print the first element, if the length of the array is 2, print a maximum of two elements.
- Create two variables value1 and value2, value1 as array[0] and value2 as maximum of array[0] and array[1] and a variable max_val to store the answer
- Traverse the array from the second element (2nd index) to the end of the array.
- For every index, update max_val as the maximum of value1 + array[i] and value2, this step defines the two cases, if an element is selected then the previous element cannot be selected and if an element is not selected then the previous element can be selected.
- For every index, Update value1 = value2 and value2 = max_val
- Print the value of max_val
Below is the Implementation of the above approach:
C++
// 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
// 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
// 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 possible : " + maxLoot(hval, n)); } } // This code is contributed by Aditya Kumar (adityakumar129) |
Python3
# 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 possible : {}".format(maximize_loot(hval, n))) if __name__ == '__main__': main() |
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) { 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 possible : " + maxLoot(hval, n)); } } // This code is contributed by Sam007 |
PHP
<?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 possible : ", maxLoot($hval, $n); // This code is contributed by ajit ?> |
Javascript
<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 possible : " + maxLoot(hval, n)); </script> |
Output
Maximum loot possible : 19
Time Complexity: O(N), Only one traversal of the original array is needed. So the time complexity is O(N).
Auxiliary Space: O(1), No extra space is required so the space complexity is constant.
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> |
Output
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).