Home » Interview coding problems/challenges

Maximum Calorie

Maximum calorie: In this article, we are going to describe a standard dynamic programming problem. It can be featured in any interview problem round.
Submitted by Radib Kar, on June 08, 2020

Problem statement

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 a_i 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

Solution Approach

Let say,

f(n) = maximum calorie can be taken till nth day under the constraint

No, let's think of the case,

1. If Shivang takes food on i^th day, he need to skip on (i-1)_^th day and sum with f(i-2)
2. Tale food on i^th day, (i-1)^th day and skip on (i-2)^th day, sum up with f(i-3)
3. Skip i^th day, so take f(i-1)

So,

f(i)=maximum(f(i-1),f(i-2)+arr[i],arr[i]+arr[i-1]+f(i-3) i>=3

For base case,
f(0)=arr[0]
f(1)=arr[0]+arr[1]
f(2)=maximum(arr[0]+arr[1],arr[1]+arr[2],arr[2]+arr[0])

Converting to Dynamic programming

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

1)  Declare int DP[n];
2)  Fill with the base case
        DP[0]=arr[0];
        DP[1]=arr[0]+arr[1];
        DP[2]=std::max(arr[1]+arr[2],std::max(arr[0]+arr[2],DP[1]));
3)  Compute the other values
        for i=3 to n-1
            DP[i]=maximum(arr[i]+arr[i-1]+DP[i-3],arr[i]+DP[i-2],DP[i-1]);
        end for
4)  Return the result, DP[n-1];

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int maximumCalorie(vector<int> arr, int n)
{

    int DP[n];
    // base case
    DP[0] = arr[0];
    DP[1] = arr[0] + arr[1];
    DP[2] = std::max(arr[1] + arr[2], std::max(arr[0] + arr[2], DP[1]));

    for (int i = 3; i < n; i++) {
        DP[i] = std::max(arr[i] + arr[i - 1] + DP[i - 3], std::max(arr[i] + DP[i - 2], DP[i - 1]));
    }

    return DP[n - 1];
}

int main()
{
    int t, n, item;
    
    cout << "Enter number of days\n";
    cin >> n;
    cout << "Enter calories\n";
    vector<int> a;
    
    for (int j = 0; j < n; j++) {
        scanf("%d", &item);
        a.push_back(item);
    }
    
    cout << "Maximum calorie sudhir can take: " << maximumCalorie(a, n) << endl;

    return 0;
}

Output

Enter number of days:
8 
Enter calories:
3 2 3 2 3 5 1 3 
Maximum calorie sudhir can take: 17