Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  228 
0

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
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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 ith day, he need to skip on (i-1)th day and sum with f(i-2)
  2. Tale food on ith day, (i-1)th day and skip on (i-2)th day, sum up with f(i-3)
  3. Skip ith 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

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

total answers (1)

interview C++ coding problems/challenges | Recursion
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Imagine you have a special keyboard with four type... >>
<< Given two positive integer n and m, find how many ...