Maximum Sum in Array/Tress: Non-adjacent index elements

One of the popular questions in an interview yet an interesting one too.
A.) House Robber I : Maximum sum given indexes are not adjacent
Key to this problem statement is the below recursive approach
rob(i) = Math.max( rob(i - 2) + currentHouseValue, rob(i - 1) )

int rob(int num[], int n) {
    int a = 0;
    int b = 0;
    
    for (int i=0; i<n; i++)
    {
        if (i%2==0)
        {
            a = max(a+num[i], b);
        }
        else
        {
            b = max(a, b+num[i]);
        }
    }
    
    return max(a, b);
}
 int rob(vector<int>& nums) { 
     int n = nums.size(), pre = 0, cur = 0;
     for (int i = 0; i < n; i++) {
        int temp = max(pre + nums[i], cur);
        pre = cur;
        cur = temp;
      }
        return cur;
    }
class Solution {
public:
    int rob(vector<int>& nums) { 
     int incl= nums[0];
     int excl = 0;
     int temp = 0;
     for(int i =1 ; i< nums.size() ; i++){
         temp = max(excl , incl);
         incl = excl + nums[i];
         excl = temp;
        }
    return max(excl , incl);
}
class Solution {
    
    public int rob(int[] nums) {
        
        int N = nums.length;
        
        // Special handling for empty array case.
        if (N == 0) {
            return 0;
        }
        
        int robNext, robNextPlusOne;
        
        // Base case initializations.
        robNextPlusOne = 0;
        robNext= nums[N - 1];
        
        // DP table calculations. Note: we are not using any
        // table here for storing values. Just using two
        // variables will suffice.
        for (int i = N - 2; i >= 0; --i) {
            
            // Same as the recursive solution.
            int current = Math.max(robNext, robNextPlusOne + nums[i]);
            
            // Update the variables
            robNextPlusOne = robNext;
            robNext = current;
        }
        
        return robNext;
    }
}
/*
My soultion : Maintain Exlude & include data at each index
*/

 int rob(vector<int>& nums) {
   int prev_inc = nums[0]; 
   int prev_exc = 0 ;
   int  curr_exc = INT_MIN ;
   int curr_inc = nums[0];
   for(int i = 1 ; i< nums.size() ; i++){
         
     curr_exc = max(prev_exc , prev_inc);
     curr_inc = prev_exc+nums[i];
            
      prev_exc = curr_exc;
      prev_inc = curr_inc;
            
   }
return max(prev_exc , prev_inc);

B.) 213. House Robber II

This problem is a little tricky at first glance. However, if you have finished the House Robber problem, this problem can simply be decomposed into two House Robber problems.
Suppose there are n houses, since house 0 and n - 1 are now neighbors, we cannot rob them together and thus the solution is now the maximum of

Rob houses 0 to n - 2;
Rob houses 1 to n - 1.
The code is as follows. Some edge cases (n < 2) are handled explicitly.

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size(); 
        if (n < 2) return n ? nums[0] : 0;
        return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
    }
private:
    int robber(vector<int>& nums, int l, int r) {
        int pre = 0, cur = 0;
        for (int i = l; i <= r; i++) {
            int temp = max(pre + nums[i], cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
};

C.) Non Adjacent tree Node

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int tryRob(TreeNode* root, int& l, int& r) {
        if (!root)
            return 0;
            
        int ll = 0, lr = 0, rl = 0, rr = 0;
        l = tryRob(root->left, ll, lr);
        r = tryRob(root->right, rl, rr);
        
        return max(root->val + ll + lr + rl + rr, l + r);
    }

    int rob(TreeNode* root) {
        int l, r;
        return tryRob(root, l, r);
    }
};

Basically you want to compare which one is bigger between 
1) you + sum of your grandchildren and 
2) sum of your children.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error

Enjoy this blog? Please spread the word :)

0
Would love your thoughts, please comment.x
()
x