You are planning to rob houses on a specific street, and you know that every house on the street has a certain amount of money hidden. The only thing stopping you from robbing all of them in one night is that adjacent houses on the street have a connected security system. The system will automatically trigger an alarm if two adjacent houses are broken into on the same night.

Given a list of non-negative integers nums representing the amount of money hidden in each house, determine the maximum amount of money you can rob in one night without triggering an alarm.

Example

For nums = [1, 1, 1], the output should be

solution(nums) = 2.

The optimal way to get the most money in one night is to rob the first and the third houses for a total of 2.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer nums

  An array representing the amount of money that each house on the street has.

  Guaranteed constraints:

  0 ≤ nums.length ≤ 100,

  0 ≤ nums[i] ≤ 500.

• [output] integer

풀이

int solution(int[] nums) {
    // 길이 = 0 이면 0 리턴
    if (nums.length == 0) return 0;
    // 길이 = 1 첫번째 수 리턴
    if (nums.length == 1) return nums[0];
    // 길이 = 2 1, 2 번째 중 큰 수 리턴
    if (nums.length == 2) return Math.max(nums[0], nums[1]);
    
    // 여태 털어왔던 돈 중 가장 많은 비용을 인덱스에 저장
    int [] arr = new int [nums.length];
    // 초기 세팅
    arr[0] = nums[0];
    arr[1] = Math.max(nums[0], nums[1]);
    
    // 현재까지 털 수 있는 가장 많은 돈은
    // 이이전 집까지 턴 최고액 + 지금 집 돈 vs 이전 집까지 턴 최고액을 비교해서 큰 것이 최고액이다.
    for (int i = 2; i < nums.length; i ++) {
        arr[i] = Math.max(arr[i - 2] + nums[i], arr[i - 1]);
    }
    
    return arr[nums.length - 1];
}