House Robber
1D DP DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Dynamic Programming: House Robber (Circular Houses Variant), Dynamic Programming, Arrays, Space Optimization, Time Complexity, Space Complexity, dynamic programming, array manipulation, iterative optimization, array algorithms, time complexity analysis, DP on Subsequences / Subsets, Circular Arrays, Array Reduction, DP Advanced Techniques.
Problem Statement: A thief needs to rob money in a street. The houses in the street are arranged in a circular manner. Therefore, the first and the last house are adjacent to each other. The security system in the street is such that if adjacent houses are robbed, the police will get notified. Given an array of integers Arr which represents money at each house, return the maximum amount of money that the thief can rob without alerting the police. Example: Input: Arr = [1, 5, 1, 2, 6] Output: 11 Explanation: If the thief robs house 5 and house 6 (values 5 and 6), the total money is 11. Houses 5 and 6 are not adjacent in the circular arrangement because house 1 is between them, and house 1 is connected to house 6. In a circular arrangement, 1 and 6 are adjacent. The set of robbed houses cannot include both house 1 and house 6. The solution considers two scenarios: either house 1 is not robbed or house 6 is not robbed. By taking the maximum of these two scenarios, the optimal solution is found.