A list of n days is given to you and there are three columns. One is the day, the second one is high-effort value, and the another one is low-effort value

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-05-01

287

High-effort vs. Low-effort Task Problem

A list of n days is given to you and there are three columns. One is the day, the second one is high-effort value, and the another one is low-effort value. At a time you can pick only one either high-effort value or low-effort value. You can pick a high-effort task only when you don't take any of the tasks at the day before. You have to find out the maximum task is possible in n days.

Input:
T Test case
T no. of input string will be given to you.

E.g.
2

Day	High	Low
1	4	3
2	5	6
3	9	4
4	12	5
5	5	4

Day	High	Low
1	2	3
2	4	2
3	7	8
4	9	7
5	10	6

Constrain:
1≤ n ≤50

Output:
Print the maximum task is possible in n days.

Example

T=2

Input:
5
4 5 9 12 5
3 6 4 5 4 

Output:
26 ( 4+ 6+ 12+ 4)

Input:
5
2 4 7 9 10
3 2 8 7 6

Output:
26 (3+2+8+7+6)

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-05-01

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

To solve this task problem using dynamic programming approach, we consider these two conditions,

If we will choose the low effort task then we have to add up this value with the value at (i-1)th index of the calculating array.
If we will choose the high effort task then we have to add up this value with the value at (i-2)th index of the calculating array.

After getting the value we will choose the maximum value between them.

Example:

5
4 5 9 12 5
3 6 4 5 4

C++ Implementation:

#include <iostream>
using namespace std;

int max_amount(int* high, int* low, int n)
{
    int arr[n + 1] = { 0 };
    arr[1] = max(high[0], low[0]);

    for (int i = 2; i <= n; i++) {
        arr[i] = max(arr[i - 1] + low[i - 1], arr[i - 2] + high[i - 1]);
    }

    return arr[n];
}

int main()
{
    int t;

    cout << "Test Case : ";
    cin >> t;

    while (t--) {
        int n;

        cout << "Enter the number of elements : ";
        cin >> n;

        cout << "Enter the High values : ";
        int high[n], low[n];
        for (int i = 0; i < n; i++) {
            cin >> high[i];
        }

        cout << "Enter the low values : ";
        for (int i = 0; i < n; i++) {
            cin >> low[i];
        }

        cout << "Maximum values : " << max_amount(high, low, n) << endl;
    }

    return 0;
}

Output

Test Case : 2
Enter the number of elements : 5
Enter the High values : 4 5 9 12 5
Enter the low values : 3 6 4 5 4
Maximum values : 26
Enter the number of elements : 5
Enter the High values : 2 4 7 9 10
Enter the low values : 3 2 8 7 6
Maximum values : 26

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

total answers (1)