package Leetcode.DynamicProgramming;

import java.util.Arrays;

/**
 * @author zhengstars
 * @date 2024/08/19
 */
public class HouseRobberII {
    /**
     * Calculates the maximum amount of money that can be robbed from a circular street of houses
     * without alerting the police.
     * @param nums an integer array representing the amount of money in each house
     * @return the maximum amount of money that can be robbed
     */
    public static int rob(int[] nums) {
        // If there is only one house, rob it and return its value
        if (nums.length == 1) {
            return nums[0];
        }

        // Case 1: Rob houses from index 0 to n-2 (excluding the last house)
        // This array includes houses from the first house to the second-to-last house.
        int rob1 = robLinear(Arrays.copyOfRange(nums, 0, nums.length - 1));

        // Case 2: Rob houses from index 1 to n-1 (excluding the first house)
        // This array includes houses from the second house to the last house.
        int rob2 = robLinear(Arrays.copyOfRange(nums, 1, nums.length));

        // Return the maximum amount that can be robbed from either case
        return Math.max(rob1, rob2);
    }

    /**
     * Helper method to calculate the maximum amount of money that can be robbed
     * from a linear street of houses.
     * @param nums an integer array representing the amount of money in each house
     * @return the maximum amount of money that can be robbed
     */
    private static int robLinear(int[] nums) {
        int prev = 0, curr = 0;
        // Iterate through the array to compute the maximum amount of money that can be robbed
        for (int num : nums) {
            // Calculate the new maximum amount that can be robbed including the current house
            int temp = curr;
            curr = Math.max(prev + num, curr);
            prev = temp;
        }
        return curr;
    }

    public static void main(String[] args) {
        // Test case 1: Rob houses with amounts [2, 3, 2]
        // Expected output: 3 (rob house 2)
        int[] nums1 = {2, 3, 2};
        System.out.println("Maximum amount for [2, 3, 2]: " + rob(nums1));

        // Test case 2: Rob houses with amounts [1, 2, 3, 1]
        // Expected output: 4 (rob house 1 and house 3)
        int[] nums2 = {1, 2, 3, 1};
        System.out.println("Maximum amount for [1, 2, 3, 1]: " + rob(nums2));

        // Test case 3: Rob houses with amounts [1, 2, 3]
        // Expected output: 3 (rob house 3)
        int[] nums3 = {1, 2, 3};
        System.out.println("Maximum amount for [1, 2, 3]: " + rob(nums3));
    }
}