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.