Largest sum of elements with no three consecutive

Given a sequence of  positive numbers, find the maximum sum that can be formed which has no 3 consecutive elements present.

For example: consider the sequence 3000 2000 1000 3 10  Here,  the answer would be 5013, by taking 3000, 2000, 3 & 10. Note that we can't form a sequence that takes 3000, 2000 & 1000 together because they are the consecutive elements of the array.

Sample cases 1 2 3                            ans=5 

100 1000 100 1000 1                        ans=2101 

1 1 1 1 1                                            ans=4 

1 2 3 4 5 6 7 8                                   ans=27

Try to find an O(N) solution. N is the number of elements in the array. 

Solution :

The solution for this problem is by dynamic programing as given below in code.

Complexity :

• Time : O(N)
• Space : O(N)

Code :

int max_three(int[] input, int N){

int sum[] = new int[N+2];

sum[0] = 0;

sum[1] = input[0];

sum[2] = input[0] + input[1];

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

    sum[i+1] = max(input[i] + sum[i-1], input[i] + input[i-1] + sum[i-2]);

    sum[i+1] = max(sum[i+1], sum[i]);

}

return sum[N];

}