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 approachrob(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);
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; } };
/** * 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.