New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

House Robber

Contributed by

Ratnesh

Medium

0/80

Avg time to solve 35 mins

Success Rate 80 %

0 upvotes

Problem Statement

Mr. X. is a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden.

Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two neighboring houses were broken into the same night.

You are given an array/list of non-negative integers 'A' representing the amount of money hidden at each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.

Example:

Input: [1,2,3,1]

Output: 4

Mr. X. can rob the first house and the third house, total money = 1 + 3.
Hence, the total money robbed by Mr. X. is 4.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains one integer 'N' denoting the size of array 'A'.

The second line of each test case contains 'N' single space-separated integers, elements of the array 'A'.

Output format :

For each test case, Return the maximum amount of money Mr. X can rob tonight without alerting the police.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10^5
0 <= A[i] <= 10ٰ^9

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

14
14

Explanation Of Sample Input 1 :

For the first case:

Input: [4,1,6,10]

Output: 4

Mr. X. can rob the first house and the fourth house, total money = 4 + 10.
Hence, the total money robbed by Mr. X. is 14.

For the second case:

Input: [2,5,8,9,1]

Output: 14

Mr. X. can rob the second and fourth houses, total money = 5 + 9.
Hence, the total money robbed by Mr. X. is 14.

Sample Input 2 :

2
8
6 1 50 1 50 30 6 100
6
55 19 21 13 10 67

Sample Output 2 :

206
143

Auto

Console