Facebook

  www.facebook.com
  www.facebook.com

Interview Question

Intern Interview

You are given an array full of positive integers. Write a

  function that returns the largest sum you can get by adding together numbers in non-adjacent indices from the array. I.e. you if you include the things stored in arr[i] in your sum, you can't include what is stored in arr[i-1] or arr[i+1]
Answer

Interview Answer

1 Answer

2

public static int subsetSumNoAdj(int[] a, int end) {
        if (end < 2) {
            return a[end];
        }
        return Math.max(a[end] + subsetSumNoAdj(a, end - 2), subsetSumNoAdj(a,
                end - 1));
    }

john doe on Jun 6, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.