×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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

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


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.