# Maximum Calorie

Shivang is very foodie but he has a diet plan. He has an array of elements indicating the calorie of food he can consume on that day. In his diet plan, he can’t eat on for three consecutive days. But since Shivang is very foodie, so he decided to take as much as calorie while remembering the fact that he cannot eat on three consecutive days. Help him in finding the number of calories he could take.

**Input:**

**n** i.e number of days. In the next line is **n** space-separated values of **ai** indicating the intake of calorie per day.

**Output:**

Print the maximum amount of calorie, Shivang can take in a new line.

**Constraints:**

1<=n<=100000
1<=ai<=100000

**Example:**

Input:
2
n=5
Array input, calorie for each day:
3 2 1 10 3
Output:
18
Explanation:
Shivang will eat on 1st, 2nd, 4th and 5th day
So, total he intakes 18 which is maximum
Input:
8
3 2 3 2 3 5 1 3
Output:
17
Explanation:
Shivang will eat on 1st, 3rd, 5th , 6th and 8th
day which totals (3+3+3+5+3) = 17

Let say,

No, let's think of the case,

ithday, he need to skip on(i-1)thday and sum withf(i-2)ithday,(i-1)thday and skip on(i-2)thday, sum up withf(i-3)ithday, so takef(i-1)So,

Converting to Dynamic programmingNow, we need to convert the above recursion into dynamic programming to avoid the overlapping sub-problem re-computation

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: