# 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;
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;
int prev_exc = 0 ;
int  curr_exc = INT_MIN ;
int curr_inc = nums;
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;
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 