LeetCode 213. House Robber II

Very interesting question 0 ~ n - 2 また 1 ~ n -1 に２つに分けることを思いつかなかったな。

class Solution {
    public int rob(int[] nums) {
        
        int n = nums.length;
        if (n <= 3){
            int max = 0;
            for (int i = 0; i < n; i++){
                max = Math.max(nums[i], max);
            }
            return max;
        }
        
        return Math.max(findMaxSum(nums, 0, n - 1), findMaxSum(nums, 1, n));
       
    }
    
    private int findMaxSum(int[] nums, int start, int end){
        int prev = 0;
        int beforePrev = 0;
        
        for (int i = start; i < end; i++){
            //prev -> beforePrev
            //prev -> new max
            int temp = prev;
            //rob or not
            prev = Math.max(beforePrev + nums[i], prev);
            beforePrev = temp;
        }
        
        return prev;
    }
}