CareerCup

Correction

public class Maximize
{
public int findMax(int[] r)
{
int[] m = new int[r.length];
for(int i=0; i<r.length; i++)
{
m[i] = r[i];
if(i >=3)
{
m[i] += Math.max(m[i-3], m[i-2]);
}
else if(i == 2)
{
m[i] += m[i-2];
}
}
return m[r.length-1];
}
}

dp

public static int findMaxProfit(int [] wealth){
		int max = Integer.MIN_VALUE;
		int [] dp = new int [wealth.length];
		
		//starting from 0
		dp [0] = wealth [0];
		
		//starting from 1
		dp [1] = wealth [1];
		for (int i = 2; i<wealth.length ;++i){
			for (int j = 0; j<i-1;++j){
                 dp [i] = dp[i] >= wealth[i] + dp[j]? dp[i] :  wealth[i] + dp[j];
				max =Math.max(max, dp[i]);
			}
		}		
		return max;

}

public static int findMaxSumOfNonAdjacents(int[] arr, int ind, int curSum) {
		
		if(ind >= arr.length)
			return curSum;
		else if(ind == arr.length-1)
			return arr[ind]+curSum;
		else
			return Math.max(findMaxSumOfNonAdjacents(arr, ind+2, curSum+arr[ind]), 
							findMaxSumOfNonAdjacents(arr, ind+1, curSum));
	}

DP, recursive function:

f(n) = max( A[n] + f(n-2), A[n-1]+f(n-3) ), if n > 1
f(n) = A[0] , if n == 0
f(n) = 0 , if n < 0

C++ algorithm:

int maxSum(int arr [], int n)
{
    int secArr [n+1];
    
    //Base cases
    secArr[0] = arr[0];
    secArr[1] = max(arr[1],arr[0]);
    secArr[2] = max(arr[2]+secArr[0],
                    arr[1]);
    //Other cases
    for (int i = 3; i <= n; i++)
    {
        secArr[i] = max(arr[i]+secArr[i-2],
                        arr[i-1]+secArr[i-3]);
    }
    return secArr[n];
}

func whichHouseToRob(allHouses:[Int])->[Int]{

    var housesToRob :[Int] = Array()
    var skippedHouses : Dictionary<Int,Int> = Dictionary()
    
    for var i = 0; i < allHouses.count; i++ {
        
        if i == allHouses.count - 1 {
            if skippedHouses[allHouses[i - 1]] != nil{
                housesToRob.append(allHouses[i])
                
            }else{
                if allHouses[i] > allHouses[i - 1]{
                    housesToRob.append(allHouses[i])
                }
            }
            break
        }
        if allHouses[i] > allHouses[i + 1]{
            housesToRob.append(allHouses[i])
            i = i + 1
            skippedHouses[allHouses[i]] = allHouses[i]
        }
        
    }
    
    
    return housesToRob
}

public class Solution {
    public int rob(int[] num) {
        if(num == null || num.length == 0){
            return 0;
        }
        
        int even = 0;
	    int odd = 0;
 
    	for (int i = 0; i < num.length; i++) {
	    	if (i % 2 == 0) {
		    	even += num[i];
			    even = even > odd ? even : odd;
		    } else {
			    odd += num[i];
			    odd = even > odd ? even : odd;
		    }
		    System.out.println("Even:"+even+" - Odd:"+odd);
	    }
    return even > odd ? even : odd;        
    }
}

Classic House Robber Prob!

// House Robber

func rob(array:[Int]) -> Int{
if(array.count == 0)
{
return 0
}

var even = 0
var odd = 0

for var i=0; i < array.count; i++
{
if(i % 2 == 0){
even += array[i]
even = even > odd ? even : odd
}else{
odd += array[i]
odd = even > odd ? even : odd
}
println("Even:\(even) - Odd: \(odd)")
}
return even > odd ? even : odd

}

rob([1,3,4,7])

DP approach o(n) space
maxProfit(i) = max(maxProfit(i-2), maxProfit(i-3))

public class Maximize
	{
		public int findMax(int[] r)
		{
			int[] m = new int[r.length];
			for(int i=0; i<r.length; i++)
			{
				m[i] = a[i];
				if(i >=3)
				{
					m[i] += Math.max(m[i-3], m[i-2]);
				}
			}
			return m[r.length-1];
		}
	}

In other words we have to find max sum such that no two elements are adjacent.
Code

private static void findMaxSum(int arr[]) {
	int incl = arr[0];
	int excl = 0;
	int excl_new;
	int i;
	for (i = 1; i < arr.length; i++) {
		excl_new = Math.max(incl, excl);
		incl = excl + arr[i];
		excl = excl_new;
	}
	System.out.println(Math.max(incl, excl));
}

Space O(1), time O(n)
Refer to geeksforgeeks for details.