import java.util.Arrays;

/**
 * 213 打家劫舍II
 */

public class Rob2 {
    public int rob(int[] nums) {
        int res = nums[0];
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        res = Math.max(res, dp(0, nums.length-2, nums, memo));
        Arrays.fill(memo, -1);
        res = Math.max(res, dp(1, nums.length-1, nums, memo));
        return res;
    }

    // 从右往左迭代
    int dp(int start, int end, int[] nums, int[] memo) {
        if(end<start) {
            return 0;
        }
        if(memo[end]!=-1) {
            return memo[end];
        }

        memo[end] = Math.max(dp(start,end-1, nums, memo),
                dp(start, end-2,  nums, memo)+nums[end]);

        return memo[end];
    }


}