Interview Question for Software Engineer at Facebook:

Max(i) = max(Ni + Max(i+2), Max(i + 1))

public int findMaxNonAdjacentSequence(int[] nums) {
  int[] max = new int[nums.length + 2];

  for (int i = nums.length - 1; i >= 0; i--) {
    max[i] = Math.max(nums[i] + max[i + 2], max[i + 1]);
  }

  return max[0];
}

If memory is concern, you can just keep the last two max values.

This won't work if the number are more than 2 places apart.
For example: this sequence:
1, -1, -2, -3, 3
the max is 4 .

It works just fine even for 1, -1, -2, -3, 3

In js:

function getMaxSubsequence(arr) {
    var maxFrom = {};
    function getMax(start, end) {
        var len = end-start+1, x1, maxSkip1, maxSkip2;

        if (maxFrom[start]===undefined) {
            if (len<1) {
                return 0;
            } else if (len==1) {
                return arr[start];
            } else if (len==2) {
                return Math.max(arr[start],arr[end]);
            } else {
                x1 = arr[start],
                maxSkip1 = getMax(start+1,end),
                maxSkip2 = getMax(start+2,end);
                maxFrom[start] = Math.max(x1+maxSkip2,maxSkip1);
            }
        }
        return maxFrom[start];
    };

    return getMax(0, arr.length-1);
}

If numbers are not positive, just put:
 max[i] = Math.max(nums[i] + max[i + 2], max[i + 1], max[i + 2]);

A valid solution would be to sort the array (O(log n) ).
Then the solution is :
int sum = 0;
int index = array.length - 1;
sum = array[index] + array[index - 2] + array[index - 4]

Rakmaninof, that solution is good but you can't use the index that you specify. The question asks for numbers that are not adjacent in the original sequence. You are making sure the numbers are not adjacent after the sort. These will likely not be the same.

public void main() {
        int[] a = {5,3,5,1,8};
        int[] b = {2,4,6,9,2};
        int res = MaxSequence(a, b, 0, 0);
        System.out.println(res);
    }
public int MaxSequence(int[] a, int[] b, int i, int j) {
        if(i==a.length-1 && j== b.length-1) {
            return max(a[i],b[j]);
        } else if(i>=a.length-1 && j <= b.length-1) {
            return sum(b,j);
        }
        else if(i== a.length-1 && j< b.length-1) {
            return max(a[i],sum(b,j));
        } else if(i<a.length-1 && j==b.length-1) {
            return max(sum(a,i),b[j]);
        }
        else {
            return max(a[i]+MaxSequence(a, b, i+1, j+1),b[j]+MaxSequence(a, b, i+2, j+1));
        }
    }

    public int sum(int[] a, int i) {
        int sum=0;
        while(i<a.length) {
            sum+= a[i];
            i++;
        }
        return sum;
    }

    public int max(int a, int b) {
        if (a>b)
            return a;
        else
            return b;
    }

Using dynamic programming this can be solved this way ..

int max_sum(int arr[], int sz, int indx) {
    if(indx >= sz) return 0;
    if(dp[indx] != -1) return dp[indx];

    int a = max_sum(arr, sz, indx+1);
    int b = max_sum(arr, sz, indx+2);

    if(a > (b+arr[indx])) dp[indx] = a;
    else dp[indx] = b+arr[indx];

    return dp[indx];
}

The exact same question was asked in a Google interview.

can't we just do it using a dp similar to lis
simple O(n^2) solution is:

void print(vint &a)
{
  copy(a.begin(),a.end(),ostream_iterator<int>(cout," "));
  cout<<endl;
}

void print_seq(vint &a, vint &P, int s)
{
   int i=s;
   int p=-1;
   stack<int> out;
   while(p!=i)
   {
     out.push(a[i]);
     p=i;
     i=P[i];
   }

   while(!out.empty())
   {
      cout<<(out.top())<<" ";
      out.pop();
   }
  cout<<endl;
}

void sequence(vint &a)
{
  vint L;
  vint P;
  int n=a.size();

  L.insert(L.begin(),n,0);
  P.insert(P.begin(),n,0);

  L[0]=a[0]; P[0]=0;
  L[1]=a[1]; P[1]=1;

  for(int i=2;i<n;++i)
  {

    P[i]=i; L[i]=a[i];
    for(int j=0;j<i-1;++j)
    {
       if(a[i]+L[j]>L[i])
       {
         P[i]=j;
     L[i]=L[j]+a[i];
       }
    }
  }

  int max,maxind;
  int i=0;

  max=L[0];maxind=0;
  for(i=0;i<n;++i)
  {
    if(L[i]>max)
    {
      max=L[i];
      maxind=i;
    }
  }

  print_seq(a,P,maxind);

  cout<<"sum: "<<max<<endl;
}

if not the above O(n^2) there is an O(n) solution, however constructing the solution takes O(n^2). getting the maximum sum is fast though. please correct me if i am missing something

void subseq_opt(vint &a)
{
   vint L;
   vint P;
   int n=a.size();

   L.insert(L.begin(),n,0);
   P.insert(P.begin(),n,0);

   L[0]=a[0]; P[0]=0;
   L[1]=a[1]; P[1]=1;

   for(int i=2;i<n;++i)
   {
     if(a[i]+L[i-2] > L[i-1])
     {
       L[i]=a[i]+L[i-2];
       P[i]=P[i-2];
     }
     else
     {
        L[i]=L[i-1];
        P[i]=P[i-1];
     }
   }

   return L[L.size()-1];
}

the main problem in constructing the solution is that in this O(n) solution you cannot know for sure if a number is selected from position [i-1] or [i-2] since it always stores max sum possible till a point. so the previous could be anywhere and we will not be make it out without using O(n^2) matrix; similar to the solution of lcs. again please correct me if i am wrong