C++ Dynamic Programming Algorithm to Compute the Largest Sum of Non-Adjacent Numbers in a Circular Array

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Dynamic Programming Algorithm (C++) to Compute the Largest Sum of Non-Adjacent Numbers in a Circular Array

For the non-circle street, we know that the DP equation is:

1
2
3

F(0) = H(0)
F(1) = max(H(0), H(1))
F(n) = max(F(n - 1), F(n - 2) + H(n)) // for n >= 2

F(0) = H(0)
F(1) = max(H(0), H(1))
F(n) = max(F(n - 1), F(n - 2) + H(n)) // for n >= 2

if F(n) denotes the maximum profit the thieve gets when he/she walks to House(n). and H(n) denotes the value that he/she can rob at house n.

Now, the street is a circular so House 0 is adjacent with House n-1. But we still can use the DP equation solver however, there are two cases: House(0) is robbed or House(0) is not robbed.

So, we compare the maximum of two cases. Remember that if we rob House(0), we can’t rob House(n-1) so the maximum value is stored at F(n-2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        vector<int> f(n);
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);
        // House(0) is robbed
        for (int i = 2; i < n - 1; i ++) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i]);
        }
        int x = f[n - 2];
        // House(0) is not robbed
        f[0] = 0;
        f[1] = nums[1];
        for (int i = 2; i < n; i ++) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i]);
        }
        x = x > f[n - 1] ? x : f[n - 1];
        return x;
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        vector<int> f(n);
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);
        // House(0) is robbed
        for (int i = 2; i < n - 1; i ++) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i]);
        }
        int x = f[n - 2];
        // House(0) is not robbed
        f[0] = 0;
        f[1] = nums[1];
        for (int i = 2; i < n; i ++) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i]);
        }
        x = x > f[n - 1] ? x : f[n - 1];
        return x;
    }
};

Two O(n) scans. We can also solve this via Top Down Dynamic Programming Algorithm aka Recursion with Memoziation.

Largest Sum of Non-Adjacent Numbers (House Robber or Disappearing Coins): Dynamic Programming Algorithms

• Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Maximum Non-Adjacent Tree Sum
• C++ Dynamic Programming Algorithm to Compute the Largest Sum of Non-Adjacent Numbers in a Circular Array
• How to Maxmize Profits to Robbering in a Binary Tree using Dynamic Programming Algorithm?
• Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem
• Teaching Kids Programming – Largest Sum of Non-Adjacent Numbers (2D Version – Disappearing Coins in a Matrix)

–EOF (The Ultimate Computing & Technology Blog) —