using System;

​

public class Program

{

    public static void Main()

    {

        Console.WriteLine(RobDP(new int[]{1, 2, 3, 1}));

        Console.WriteLine(RobDP(new int[]{2, 7, 9, 3, 1}));

        Console.WriteLine(RobDP(new int[]{2, 1, 1, 2}));

        Console.WriteLine("**********");

        Console.WriteLine(RobMax(new int[]{1, 2, 3, 1}));

        Console.WriteLine(RobMax(new int[]{2, 7, 9, 3, 1}));

        Console.WriteLine(RobMax(new int[]{2, 1, 1, 2}));

        Console.WriteLine("**********");

        Console.WriteLine(Rob(new int[]{1, 2, 3, 1}));

        Console.WriteLine(Rob(new int[]{2, 7, 9, 3, 1}));

        Console.WriteLine(Rob(new int[]{2, 1, 1, 2}));

    }

​

    private static int RobDP(int[] nums)

    {

        int len = nums.Length;

        if(len == 0) return 0;

        if(len == 1) return nums[0];

        var dp = new int[len];

        dp[0] = nums[0];

        dp[1] = Math.Max(nums[0], nums[1]);

        int max = dp[1];

        for(int i = 2; i < len; i++)

        {

            dp[i] = Math.Max(dp[i - 2] + nums[i], dp[i-1]);

            max = Math.Max(max, dp[i]);

        }

        return max;

    }

    private static int RobMax(int[] nums)

    {

        int len = nums.Length;

        if(len == 0) return 0;

        var max = nums[0];

        var prev = 0;

        for(int i = 1; i < len; i++)

        {

            int temp = max;

            max = Math.Max(nums[i] + prev, max);

            prev = temp;

        }

​

        return max;

    }

    private static int Rob(int[] nums)

    {

        int robbed = 0;

        int notRobbed = 0;

        foreach (int n in nums)

        {

            int temp = notRobbed;

            notRobbed = Math.Max(robbed, notRobbed);

            robbed = n + temp;

        }

​

        return Math.Max(robbed, notRobbed);

    }

}