HackerEarth Mehta And Subarrays problem solution

In this HackerEarth Mehta And Subarrays problem solution This time your task is simple.

Task:

Mehta has to find the longest subarray whose sum is greater than equal to zero in a given array of length** N**. After he finds out the length of longest subarray, he has to report how many subarrays of such maximum length exist that satisfy the mentioned property.

Note:

Subarray is defined as an array of contiguous numbers in a particular array. Subarray(A,B) has length (B-A+1) and consists of all numbers from index A to index B.

HackerEarth Mehta And Subarrays problem solution.

#include <bits/stdc++.h>

using namespace std;

vector < pair<long long, int> > v;

int n;

int main()
{
    int n,len,cnt,mn;
    long long sum,x;
    sum = len = cnt = 0;

    cin >> n;

    v.push_back(make_pair(0,1));
    for ( int i = 1; i <= n; i++ ) {
        cin >> x;
        sum += x;
        v.push_back(make_pair(sum,i+1));
    }
    sort(v.begin(),v.end());
    mn = v[0].second;
    for ( int i = 1; i <= n; i++ ) {
        int val = max(0,v[i].second-mn);
        if ( val > len ) {
            len = val;
            cnt = 1;
        }
        else if ( val == len ) cnt++;

        mn = min(mn,v[i].second);
    }
    if ( len == 0 ) cout << "-1" << endl;
    else cout << len << " " << cnt << endl;
    return 0;
}

Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define P(x) printf("%dn",x)

typedef long long int LL;
typedef pair<LL, int > pli;
const int N = 100001;

LL A[N];

int main() {
    int n;
    S(n);

    assert(n > 0 && n < 1000001);
    rep(i,1,n+1) {
        cin >> A[i];
        assert(A[i] >= -1000000000 && A[i] <= 1000000000);
        A[i] += A[i-1];
    }

    vector<pli > st;
    int mx,cnt;
    mx = cnt = 0;
    rep(i,1,n+1) {
        if(!st.size() || st.back().first > A[i])
            st.push_back(make_pair(A[i], i));

        int cur;
        if(A[i] >= 0) {
            cur = i;
        } else {
            int lo = 0;
            int hi = (int)st.size() - 1;

            int idx = -1;
            while(lo <= hi) {
                int mi = (lo + hi) >> 1;
                if(st[mi].first <= A[i]) {
                    idx = st[mi].second;
                    hi = mi - 1;
                } else {
                    lo = mi + 1;
                }
            }
            cur = i - idx;

        }

        if(cur > mx) {
            mx = cur;
            cnt = 0;
        }
        if(cur == mx)
            cnt++;
    }
    if(mx == 0) {
        P(-1);
    } else {
        printf("%d %dn",mx, cnt);
    }
    return 0;
}

HackerEarth Mehta And Subarrays problem solution

HackerEarth Mehta And Subarrays problem solution.

Second solution

Leave a Reply

Pages

Practice