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("%d\n",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 %d\n",mx, cnt);
}
return 0;
}
0 Comments