HOSTELROOM- Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are initially X people in a room.
You are given an array A of length N which describes the following events:

  • If A_i \geq 0, then A_i people enter the room at i^{th} minute.
  • If A_i < 0, then |A_i| people leave the room at i^{th} minute.

Determine the maximum number of people in the room at any moment of time.

EXPLANATION:

We are given that there are X people in the room initially. We keep a count of the number of people in the room after each minute. This count is initialised with X.

Let Y denote the number of people in the room after the (i-1)^{th} minute. For the i^{th} minute:

  • If A_i \geq 0, the number of people in the room becomes Y' = Y+A_i.
  • If A_i < 0, the number of people in the room becomes Y' = Y-|A_i|.

We have to find the maximum number of people in the room at any time.
Thus, after each minute, we check if the number of people in the room (Y') can be a possible answer. We update the value of answer if Y' is greater than the current answer.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Tester's Solution 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    cin >> T;
    while(T--){
    
        int n,x,y;
        cin>>n>>x;

        int mx = x;
        rep(i,n){
            cin>>y;
            x+=y;
            if(x>mx) mx=x;
        }

        cout<<mx<<el;
    }
    return 0;
}
Editorialist's Solution 
#include <iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n, x;
	    cin>>n>>x;
	    int a[n];
	    for(int i = 0; i<n; i++){
	        cin>>a[i];
	    }
	    
	    int maxm = x;
	    int curr_sum = x;
	    for(int i = 0; i<n; i++){
	        curr_sum += a[i];
	        maxm = max(maxm, curr_sum);
	    }
	    cout<<maxm<<endl;
	}
	return 0;
}
4 Likes