← 返回 bytedance 的题目列表House Robber (DP)
类型：online_judge
Problem
Given an array nums of length n where nums[i] is the amount of money in the i-th house. You cannot rob two adjacent houses in the same night (i.e., you cannot pick both i and i+1).
Compute the maximum amount you can rob without triggering the alarm.
Input (stdin)
Line 1: an integer n.
Line 2: n non-negative integers representing nums.
Output (stdout)
Print one integer: the maximum amount you can rob.
Constraints
1 <= n <= 2 * 10^5
0 <= nums[i] <= 10^9
Example
Input:
4
1 2 3 1
Output:
4
Explanation: Rob house 1 and 3 (1 + 3 = 4).
Example
Input
4
1 2 3 1
Output
4