In this HackerRank Two Subarrays problem solution Let m be the length of the smallest subarray such that f(l,r) = g. Given A, find the value of g as well as the number of subarrays such that r - l + 1 = m and f(l,r) = g, then print these respective answers as space-separated integers on a single line.

HackerRank Two Subarrays problem solution


Problem solution in Java.

import javafx.util.Pair;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class F {

    BufferedReader in;
    StringTokenizer t = new StringTokenizer("");

    public static void main(String[] args) throws IOException {
        try {
            new F().run();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    int nextInt() throws IOException {
        while (!t.hasMoreTokens())
            t = new StringTokenizer(in.readLine());
        return Integer.parseInt(t.nextToken());
    }

    void update(int i, int j, int val, int a[][]) {
        while (i < a.length) {
            if (val > a[i][j])
                a[i][j] = val;
            i++;
        }
    }

    void run() throws IOException {
//        in = new BufferedReader(new FileReader("F.in"));
        in = new BufferedReader(new InputStreamReader(System.in));
        int n = nextInt();
//        int n = 200000;
        int a[] = new int[n];
        int p2[] = new int[n + 2];
        for (int i = 0; i < n; i++) {
//            a[i] = i % 40 + 1;
            a[i] = nextInt();
            p2[i + 2] = p2[(i + 2) / 2] + 1;
        }
        int table[][] = new int[1 + p2[n]][n + 1], s = 0;
        int posit[][] = new int[1 + p2[n]][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            s += a[i];
            table[0][i] = s;
            posit[0][i] = i;
        }
        for (int i = 1; i <= p2[n]; i++) {
            for (int j = 0; j < n; ++j) {
                int nx = j + (1 << (i - 1));
                if (!(nx + (1 << (i - 1)) <= n && table[i - 1][nx] >= table[i - 1][j])) {
                    nx = j;
                }
                table[i][j] = table[i - 1][nx];
                posit[i][j] = posit[i - 1][nx];
            }
        }

        int g = 0, m = 1, kol = n;
        int r[][] = new int[41][40 * 40];
        for (int i = 0; i < r.length; i++) {
            for (int j = 0; j < r[i].length; j++) {
                r[i][j] = -1;
            }
        }
        int added[] = new int[n];
        int MX = 40 * 41 / 2;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) {
                update(a[i], a[i], i, r);
                int mx = a[i] * (a[i] + 1) / 2;
                for (int j = a[i]; j <= mx; j++) {
                    if (r[a[i] - 1][j - a[i]] >= 0)
                        update(a[i], j, r[a[i] - 1][j - a[i]], r);
                }
                ArrayList<Pair<Integer, Integer>> pr = new ArrayList<>();
                pr.add(new Pair<>(-1, -1));
                for (int j = MX; j >= 1; j--) {
                    if (r[40][j] != -1 && added[r[40][j]] != i) {
                        pr.add(new Pair<>(r[40][j], j));
                        added[r[40][j]] = i;
                    }
                }
                Collections.sort(pr, (x, y) -> (x.getKey() - y.getKey()));
                int d = 0;
                for (int j = pr.size() - 1; j > 0; j--) {
                    d = Math.max(d, pr.get(j).getValue());
                    int ll = pr.get(j - 1).getKey() + 1;
                    int pp2 = p2[i - ll + 1];
                    if (table[pp2][i - ((1 << pp2) - 1)] >= table[pp2][ll])
                        ll = i - ((1 << pp2) - 1);
                    int mx1 = table[pp2][ll] - table[0][i + 1] - d;
                    int mxi = i - posit[pp2][ll];
                    if (mx1 > g || (mx1 == g && mxi < m)) {
                        g = mx1;
                        m = mxi;
                        kol = 1;
                    } else if (mx1 == g && mxi == m) {
                        kol++;
                    }
                }
            }
        }
        if (g == 0)
            System.out.println("0 " + n);
        else
            System.out.println(g + " " + kol);
    }
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <stack>
#include <stdio.h>
#include <map>
#include <set>
#include <time.h>
#include <string>
#include <fstream>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <assert.h>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pdd pair<double,double>
#define pii pair<ll,ll>
#define PI 3.14159265358979323846
#define MOD 1000000007
#define MOD2 1000000009
#define INF ((ll)1e+18)
#define x1 fldgjdflgjhrthrl
#define x2 fldgjdflgrtyrtyjl
#define y1 fldggfhfghjdflgjl
#define y2 ffgfldgjdflgjl
#define N 262134
#define SUM 23423
#define MAG 100000000
#define OPEN 0
#define CLOSE 1
typedef int ll;
typedef long double ld;
using namespace std;
ll i,j,n,k,l,m,tot, flag,r,ans,z, K,x1,y1,x2,y2,x3,y3,x,y,h,num,h2,timer,sz,q,c;
ll dp[41][821], a[200500], b[41][825], pa[200500];
pii t[500500];
void build() {  // build the tree
  for (int i = N - 1; i > 0; --i) t[i] = min(t[i<<1], t[i<<1|1]);
}

pii query(int l, int r) {  // sum on interval [l, r)
  pii res = mp(MOD,0);
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = min(res, t[l++]);
    if (r&1) res = min(res, t[--r]);
  }
  return res;
}


int main() {
    //freopen("input.txt","r",stdin);
     //freopen("output.txt","w",stdout);
     h = 820;
    for (i = 0; i <= 40; i++)
        for (j = 0; j <= h; j++)
            dp[i][j] = b[i][j] = -1;
     cin >> n;
     assert(n >= 1 && n <= 200000);
     for (i = 0; i < n; i++)
     {
        cin >> a[i];
        assert(-40 <= a[i] && a[i] <= 40);
        pa[i+1] = pa[i] + a[i];
        t[N+i+1] = mp(pa[i+1], -i-1);
    }
    build();
    ll ans = 0, len = 0, cnt = 0;
    for (i = 0; i < n; i++)
    if (a[i] > 0)
    {
        dp[a[i]][a[i]] = i;
        b[a[i]][a[i]] = i;
        ll val = a[i]*(a[i]-1)/2;
        ll to = a[i];
        //for (j = 1; j < to; j++)
            for (k = 1; k <= val; k++)
            {
                dp[to][k+to] = max(dp[to][k+to], b[to-1][k]);
                b[to][k+to] = max(b[to][k+to], dp[to][k+to]);
            }
        for (j = to+1; j <= 40; j++)
            for (k = to; k <= val+to; k++)
                b[j][k] = max(b[j][k], b[j-1][k]);
        ll cur = -1, lst = -1, cur_sum = -1;
        for (j = h; j >= a[i]; j--)
        {
            if (b[40][j] > cur)
            {
               lst = cur, cur = b[40][j], cur_sum = j;
                pii mn = query(lst+1, cur+1);
                mn.Y = -mn.Y;
                ll val1 = pa[i+1]-mn.X-cur_sum, val2 = i-mn.Y;
                if (ans < val1)
                {
                   ans = val1, cnt = 1, len = val2;
                }
                else
                if (ans == val1)
                {
                   if (val2 < len)
                      cnt = 1, len = val2;
                   else
                   if (val2 == len)
                          cnt++;
                }
            }
        }
    }
    if (ans == 0)
       cnt = n;
    cout << ans << " " << cnt << endl;
    return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include<stdio.h>
#include<stdbool.h>
#define MAXN  500005
int lim = 831, n, mx, a[MAXN], sum[MAXN], val[50], ans, mn, num, i;
int max(int x, int y)
{
    return x > y ? x : y;
}
bool flag[MAXN];
int main()
{
    scanf("%d", &n);
    for( i = 1 ; i <= n ; i++ )
    {
        scanf("%d", &a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    int mx = sum[n];
    for( i = n ; i ; i-- )
    {
        mx = max(mx, sum[i]);
        if( mx - sum[i] > lim )
        {
            flag[i] = 1;
        }
    }
    num = n;
    for( i = 1 ; i <= n ; i++ )
    {
        if(flag[i])
        {
            continue;
        }
        memset(val, 0, sizeof val);
        int now = 0, l, j;
        for( l = i ; l && ( sum[l] < sum[i] || l == i ) ; l-- )
        {
            if( a[l] > 0 )
            {
                mx = 0;
                for( j = a[l] + 1 ; j <= 40 ; j++ )
                {
                    mx = max(mx, val[j]);
                }
                val[a[l]] = max(val[a[l]], mx+a[l]);
                now = max(now, mx+a[l]);
            }
            int tmp = sum[i] - sum[l-1] - now;
            int len = i - l + 1;
            if( tmp > ans )
            {
                ans = tmp;
                mn = len;
                num = 1;
            }
            else
            {
                if( tmp == ans )
                {
                    if( mn > len )
                    {
                        mn = len;
                        num = 1;
                    }
                    else if( len == mn )
                    {
                        num++;
                    }
                }
            }
        }
    }
    printf("%d %d\n", ans, num);
}

{"mode":"full","isActive":false}