Question

Stacks & Queues
C++

You are given a stack of N integers such that the first element represents the top of the stack and the last element represents the bottom of the stack. You need to pop at least one element from the stack. At any one moment, you can convert stack into a queue. The bottom of the stack represents the front of the queue. You cannot convert the queue back into a stack. Your task is to remove exactly K elements such that the sum of the K removed elements is maximized.

Input format :
The first line consists of two space-separated integers N and K. The second line consists of N space-separated integers denoting the elements of the stack.

Output format : Print the maximum possible sum of the K removed elements

Sample Input:

10 5
10 9 1 2 3 4 5 6 7 8

Sample Output:

40

Explanation Pop two elements from the stack. i.e {10,9} Then convert the stack into queue and remove first three elements from the queue. i.e {8,7,6}. The maximum possible sum is 10+9+8+7+6 = 40

This is my code so far

#include <iostream>
#include <deque>
std::deque<int> stacque;
using namespace std;
void printDeque(deque<int> vector) {
for(int i=0;(unsigned)i<vector.size();i++) {
cout<<vector.at(i)<<" ";
}
cout<<endl;
}

int main() {
int n,q;
cin>>n;
cin>>q;
for(int i=0;i<n;i++){
int x;
cin>>x;
stacque.push_back(x);
}
/*cout<<n<<" "<<q<<endl;
printDeque(stacque);*/

int sum=0;
for(int i=0;i<q;i++){
  
if(stacque.front()>stacque.back()){
int a;
a=stacque.front();
sum+=a;
stacque.pop_front();
  
}
else {
int b;
b=stacque.back();
sum+=b;
stacque.pop_back();
  
}
}
cout<<sum<<endl;

return 0;
}


my output for the test is nearly correct but its only slightly off

input test 1

420 135
46 1 19 60 86 64 5 98 4 85 93 25 82 56 83 31 92 23 77 36 17 63 31 61 92 31 86 82 91 84 26 54 27 61 95 87 53 50 72 30 73 49 35 4 21 36 73 50 97 70 95 7 81 92 76 33 77 48 50 100 80 22 35 67 40 56 28 31 31 60 8 10 31 76 99 69 56 65 2 79 15 5 68 82 55 60 16 95 44 34 2 54 71 88 100 100 76 16 49 46 69 90 41 11 33 45 8 58 37 40 9 65 50 79 15 54 6 98 11 56 77 20 89 22 18 24 33 12 52 33 31 31 71 1 26 68 62 53 14 5 70 79 18 12 71 93 60 37 23 86 8 31 73 71 76 70 51 88 55 68 59 100 45 49 16 35 61 78 29 80 74 19 56 72 92 49 17 86 17 48 58 68 57 100 31 87 38 11 63 7 48 59 73 69 84 58 77 74 1 4 55 53 52 96 99 74 77 8 44 40 55 50 99 28 13 40 83 43 68 97 53 81 53 49 86 68 87 92 22 65 26 2 14 62 51 76 67 1 20 99 60 13 72 69 17 55 92 94 1 28 69 72 71 42 31 79 83 100 71 56 91 40 20 33 1 12 96 27 95 29 57 40 70 57 8 80 93 4 30 31 82 53 98 67 75 6 60 49 23 54 52 67 84 71 67 85 92 58 42 80 40 87 60 55 17 73 90 3 55 2 63 86 53 60 71 16 34 46 1 49 10 82 4 67 64 3 91 20 56 98 22 45 14 85 93 3 54 77 31 49 67 15 32 31 18 7 95 34 12 96 99 30 88 91 42 85 72 74 12 4 40 97 79 65 29 29 48 76 35 73 66 39 9 86 7 99 22 46 66 48 21 30 52 69 22 26 16 52 48 62 55 97 60 86 86 59 68 94 21 51 90 32 32 94 12 96 29 73 4 98 13 80 72 67 18 68 15 26 79 38
Your output
7033
Your output does not contain
7510

input test 2

Input
490 231
68 51 46 65 74 64 38 94 96 65 39 9 26 86 99 93 37 65 11 86 53 45 40 56 43 32 98 70 57 89 36 38 51 62 23 86 18 55 30 37 52 21 59 60 15 78 84 23 98 44 78 68 94 49 59 43 63 91 71 9 75 89 76 23 100 59 18 97 89 2 25 33 59 48 84 50 78 71 84 3 96 60 7 38 11 16 99 41 11 91 65 8 10 29 14 88 7 70 80 56 38 54 16 42 1 70 1 96 97 62 82 42 17 84 96 73 77 78 85 82 27 72 33 57 38 57 95 76 59 32 26 76 9 22 19 88 14 43 46 13 20 7 7 62 58 76 54 92 35 78 17 86 5 86 27 44 75 76 15 21 34 15 14 83 62 95 40 42 45 16 10 38 77 1 90 72 27 72 22 75 93 49 82 52 95 6 76 55 66 66 53 85 70 61 38 64 22 33 58 50 63 39 35 90 54 53 45 71 95 93 78 51 47 94 81 6 26 22 18 1 82 77 86 49 100 5 88 40 4 60 79 26 88 38 12 81 70 95 80 37 28 57 80 68 1 43 9 10 42 16 18 67 99 3 41 50 35 48 42 42 16 47 11 75 52 76 33 60 10 47 96 5 12 10 86 61 80 86 58 45 63 95 33 51 38 45 95 2 49 76 10 50 3 62 39 94 47 33 54 99 76 60 57 2 8 47 18 90 28 99 66 47 8 95 85 25 42 90 27 66 100 22 18 93 95 83 27 89 4 21 39 80 46 14 46 58 55 12 83 95 99 3 86 8 43 92 24 72 7 47 34 78 77 87 100 3 11 72 86 37 48 68 28 9 92 59 95 39 59 97 64 21 95 94 25 48 42 91 76 16 97 72 71 49 24 30 18 90 64 10 44 6 87 95 37 90 52 37 53 86 54 95 11 28 83 12 65 87 73 58 83 9 85 20 15 73 21 39 87 73 75 44 50 99 37 92 82 66 68 60 72 60 25 72 35 11 67 4 86 1 10 3 79 28 2 44 29 33 71 22 99 13 77 3 36 54 17 61 79 77 83 34 39 31 100 46 23 54 83 3 13 62 31 81 58 17 16 92 54 92 39 51 37 68 94 63 73 26 45 1
Your output
12257
Your output does not contain
12595

i passed one of the tests but these 2 are only slightly off and i dont know why.
please provide a solution in C++

Answer 1

Code:

#include <bits/stdc++.h>
#define ll long long
#define MAX 2000000
using namespace std;
int main() {
    ll n,k;
    // Take the number input
    cin>>n>>k;
    // Declare array 
    ll arr[n+1];
    // Take the array input
    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }
    // Declare array to store prefix sum
    ll prefix[n+1];
    // Initialize prefix array
    prefix[0]=arr[0];
    // Calculate ans store prefix sum in the prefix array
    for(int i=1;i<n;i++) {
        prefix[i]=prefix[i-1]+arr[i];
    }
    // Declare and initialize variable to store answer 
    ll ans=0;
    // Loop 0 until k-1 (k times)
    for(int i=0;i<k;i++){
        // sliding window of size k to calculate the maxsum
        ll temp=prefix[i]+prefix[n-1]-prefix[n-k+i];
        ans=max(ans,temp);
    }
    cout<<ans;
    return 0;
}

Screenshots:

Output:

-------------------------END---------------------

Please give a thumbs up(upvote) if you liked the answer.