Program to find Maximum sum such that no two elements are adjacent

Algorithm :

1) sum[i-1] (NOTE:sum[i] may or may not include a[i-1]). Since we are not including a[i] so while calculating sum[i+1], a[i] will surely be missing.This will ensure us with no consecutive element present in our calculation.

2) a[i] + sum[i-2], this will insure that we are not including a[i-1], so if S[i-2] has a[i-2], again no adjacent element will be together.

so our entire algorithm can be summarized as:
sum[i] = max( sum[i-1] , sum[i-2] + a[i-1] )