Maximum possible sum of Non-consecutive elements

There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum.

Example: If given array is (6, 4, 2, 8, 1), the answer will be 14 (8+6). This is the maximum sum we can obtain without taking two consecutive elements.

Method 1:

To solve these type of question, first thing is to find a recurring relation. In this case our recurring relation will tell the max sum till a given length. It means that we will get the max sum for running length of the array. If we denote the ith element as T(i) and max sum till ith element of the array as S(i), then

S(i) = MAX {S(i-1), S(i-2) + T(i) }

S(-1) = 0;
if i=0, S(i) = T(0);

Note: while developing this relationship, I assume array index is starting from 0.

sum2 = 0;
sum = sum1 = array[0];
for(i=1; i<len; i++)
{
   sum = MAX(sum2 + array[i], sum1);
   sum2 = sum1;
   sum1 = sum;}
Method 2:Dynamic Programming

This is a problem of Dynamic Programing and similar to longest increasing sub-sequence with the restriction that the sub-sequence cannot contain adjacent elements. The only difference is that in that problem, for an index j all the indices i, such that i < j were considered. But here we will consider i, such that i < j-1
The problem (and the longest sub-sequence as well) can be solved by modeling the array as a graph with an edge between (i,j) if j>i where j and i are the indices of the numbers but not when i = j-1 i.e. the two numbers are adjacent.

Pseudo Code:

  Create an array L[N]
for j = 1 to N:
    L(j) = a(j) + max{L(i) : (i; j) belongs to E}
return max L(j)

the base case will be when j=1 
max{ L(i): (i,j) belongs to E}= 0

The solution has O(N2) time complexity and O(N) space complexity.