class Solution {
    public int rob(int[] nums) {
        //same question as house robber just circular array , both last index and first 
        //index cant be in 1 solution ....make 2 arrays for both and return max answer
        // out of the two of them
        int n = nums.length;
        if(n == 1)
        return nums[0];

        int[] copy1 = Arrays.copyOfRange(nums, 0, n-1);     //0 to n-2
        int[] copy2 = Arrays.copyOfRange(nums, 1, n);       //1 to n-1


        //memoization solution
        // return Math.max(solve(temp1 , n-2 , new Integer[n-1]) , solve(temp2 , n-2 , new Integer[n-1]));

        return Math.max(solve2(copy1) ,solve2(copy2));
    }
    
    //tabulization from House Robber 1
    public int solve2(int nums[]){
        int n = nums.length;
        int dp[]= new int[n];
        dp[0] = nums[0];

        for(int i = 1 ;i < n ; i++){
            
           int pick = nums[i] + (i-2 >= 0 ? dp[i-2] : 0);

            int notpick = 0 + dp[i-1];

            dp[i] = Math.max(pick ,notpick);
        }
        return dp[n-1];
    }
    //recursion + memoization
    public int solve(int[] nums , int idx , Integer[] dp){
        if(idx == 0 )
        return nums[0];

        if(idx < 0)
        return 0;

        if(dp[idx] != null)
        return dp[idx];

        int pick = nums[idx] + solve(nums ,idx-2 , dp);
        int notpick = 0 + solve(nums , idx-1 , dp);

        return dp[idx] = Math.max(pick , notpick);
    }
}