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

*space-separated values of*

**n***indicating the intake of calorie per day.*

**a**_{i}**Output:**

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

**Constraints:**

1<=n<=100000 1<=a_{i}<=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,

- If Shivang takes food on
*i*day, he need to skip on^{th}*(i-1)*day and sum with^{th}*f(i-2)* - Tale food on
*i*day,^{th}*(i-1)*day and skip on^{th}*(i-2)*day, sum up with^{th}*f(i-3)* - Skip
*i*day, so take^{th}*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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.