HackerRank Two Subarrays Problem Solution

In this post, we will solve HackerRank Two Subarrays Problem Solution.

We define the following functions:
sum(l, r) = ai +at+1+…+ar
inc(l,r) = the maximum sum of some strictly increasing subsequence in subarray
A[l, r
f(l, r) sum(l,r) – inc(l,r)
We define the goodness, g, of array A to be:
g= max f(l, r) for 0 < 1 < r < n
In other words, g is the maximum possible value of f(l, r) for all possible subarrays of array A.
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-1+1=m and f(l, r) = g. then print these respective answers as space-separated integers on a single line.
Input Format
The first line contains an integer, n, denoting number of elements in array A.
The second line contains n space-separated integers describing the respective values of
a0, a1,…,an-1.

Sample Input 0

3
2 3 1

Sample Output 0

1 1

Explanation 0

The figure below shows how to calculate g:

m is the length of the smallest subarray satisfying f(l, r). From the table, we can see that m = 2. There is only one subarray of length 2 such that f(l, r) = g=1.

HackerRank Two Subarrays Problem Solution

Two Subarrays C Solution

#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);
}

Two Subarrays C++ Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int kSum = 40 * 21 + 30;
const int N = 200005;

int arr[N];
int acc_sum[N];
int n;

struct SparseTable {
  int log_2[N];
  int table[N][19];
  int n;

  void Build() {
    n = ::n + 1;
    int cnt = -1;
    for (int i = 0; i < n; i++) {
      if (!((i + 1) & i)) cnt++;
      table[i][0] = i;
      log_2[i + 1] = cnt;
    }
    for (int j = 1; (1 << j) <= n; j++) {
      for (int i = 0; (i + (1 << j)) <= n; i++) {
        int a = table[i][j - 1];
        int b = table[i + (1 << (j - 1))][j - 1];
        table[i][j] = ((acc_sum[b] > acc_sum[a]) ? b : a);
      }
    }
  }

  int GetMax(int st, int en) {
    int log_ = log_2[en - st + 1];
    int a = table[st][log_], b = table[en - (1 << log_) + 1][log_];
    return ((acc_sum[b] > acc_sum[a]) ? b : a);
  }
} sparse_table;

void BuildAccSum() {
  for (int i = 1; i <= n; ++i) {
    acc_sum[i] = arr[i] + acc_sum[i - 1];
  }
}

void Print(const vector<int>& v) {
  for (int i = 1; i < 30; ++i) {
    if (v[i] == n + 1) continue;
    cout << "(" << i << " : " << v[i] << ") ";
  }
  cout << endl;
}

void Update(int ind, const vector<int>& sequence_sums_indices, int& g,
  int& cnt_ranges, int& range_size) {
  int right = n + 1;

  for (int j = kSum - 1; j > 0; --j) {
    if (sequence_sums_indices[j] >= right) continue;

    int r = sparse_table.GetMax(sequence_sums_indices[j], right - 1);
    right = sequence_sums_indices[j];

    int tmp_g = acc_sum[r] - acc_sum[ind - 1] - j;

    if (tmp_g < g) continue;
    if (tmp_g > g) {
      g = tmp_g;
      range_size = r - ind + 1;
      cnt_ranges = 1;
    } else {
      if (r - ind + 1 < range_size) {
        range_size = r - ind + 1;
        cnt_ranges = 1;
      } else if (r - ind + 1 == range_size) {
        ++cnt_ranges;
      }
    }
  }
}

int g;
int cnt_ranges;
int range_size;

vector<int> UpdateSSI(const vector<int>& v, int ind) {
  vector<int> res(v);
  for (int i = kSum - 41; i > 0; --i) {
    res[i + arr[ind]] = min(v[i + arr[ind]], v[i]);
  }

  return res;
}

void Minimize(vector<int>& v1, const vector<int>& v2) {
  for (int i = 1; i < kSum; ++i) {
    v1[i] = min(v1[i], v2[i]);
  }
  assert(v1.back() == n + 1);
}

void BuildSequenceSumsIndices() {
  vector<int> curr_sequence_sums_indices(kSum);

  for (int& x : curr_sequence_sums_indices) {
    x = n + 1;
  }

  vector<int> seq_sums_indices[42];
  int pos[42];
  for (int& x : pos) {
    x = n + 1;
  }
  for (auto& v : seq_sums_indices) {
    v.resize(kSum);
    for (int& x : v) {
      x = n + 1;
    }
  }

  for (int i = n; i > 0; --i) {
    if (arr[i] <= 0) continue;

    for (int& x : seq_sums_indices[arr[i]]) {
      x = n + 1;
    }

    seq_sums_indices[arr[i]][arr[i]] = i;


    int right = n + 1;
    for (int j = arr[i] + 1; j <= 40; ++j) {
      if (pos[j] >= right) continue;
      auto tmp = UpdateSSI(seq_sums_indices[j], i);
      Minimize(seq_sums_indices[arr[i]], tmp);
      right = pos[j];
    }
    pos[arr[i]] = i;
    Minimize(curr_sequence_sums_indices, seq_sums_indices[arr[i]]);
    Update(i, curr_sequence_sums_indices, g, cnt_ranges, range_size);
  }

}

pair<int, int> Solve() {
  g = 0;
  cnt_ranges = 0;
  range_size = n + 1;

  BuildSequenceSumsIndices();

  if (g == 0) {
    cnt_ranges = n;
  }

  return {g,cnt_ranges};
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
//  freopen("test.in", "r", stdin);
//  freopen("out.txt", "w", stdout);
#endif
  cin >> n;

  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
  }

  BuildAccSum();
  sparse_table.Build();

  auto res = Solve();

  cout << res.first << ' ' << res.second;
}

Two Subarrays C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;


class Solution {
    static void Main(string[] args) {
        int n = Convert.ToInt32(Console.ReadLine());

        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp));
              
        Solve(a);
    }

            public static void Solve(int[] input)
        {
            long max_f = 0, counter1=0, delka1 = 1;
            long[] results = new long[2];
            long[] sum = new long[input.Length];

            List<int> lowerBound = new List<int>();
            List<int> upperBound = new List<int>();

            bool negative, positive;
            sum[0] = input[0];
            
            if (sum[0] <= 0)
            {
                negative = true;
                positive = false;
                sum[0] = 0;
            }
            else
            {
                negative = false;
                positive = true;
                lowerBound.Add(0);
            }

            for (int i = 1; i < input.Length; i++)
            {
                sum[i] = sum[i-1] + input[i];
                if (sum[i] <= 0 && positive)
                {
                    upperBound.Add(i);
                }
                else if (sum[i] > 0 && negative)
                {
                    lowerBound.Add(i);
                    negative = false;
                    positive = true;
                }

                if (sum[i] <= 0)
                {
                    sum[i] = 0;
                    negative = true;
                    positive = false;
                }
            }

            upperBound.Add(input.Length);

            for (int i = 0; i < lowerBound.Count; i++)
            {
                results = wrapper2(input.Skip(lowerBound[i]).Take(upperBound[i] - lowerBound[i]).ToArray());

                
                if (results[0] > max_f)
                {
                    max_f = results[0];
                    counter1 = results[1];
                    delka1 = results[2];
                }
                else if (results[0] == max_f)
                {
                    if (results[2] < delka1)
                    {
                        delka1 = results[2];
                        counter1 = results[1];
                    }

                    else if (results[2] == delka1)
                    {
                        counter1 += results[1];
                    }
                }
            }

            if (max_f == 0)
            {
                counter1 = input.Length;
            }

            Console.WriteLine(max_f + " " + counter1);
        }


        public static long getSum(long[] BITree, long index)
        {
            long sum = 0;
            while (index > 0)
            {
                sum = Math.Max(sum, BITree[index]);
                index -= index & (-index);
            }

            return sum;
        }

        // Updates a node in Binary Index 
        // Tree (BITree) at given index in 
        // BITree. The max value is updated 
        // by taking max  of 'val' and the 
        // already present value in the node. 
        public static void updateBIT(long[] BITree, long newIndex, long index, long val)
        {
            while (index <= newIndex)
            {
                BITree[index] = Math.Max(val, BITree[index]);
                index += index & (-index);
            }
        }

        // maxSumIS() returns the maximum 
        // sum of increasing subsequence 
        // in arr[] of size n 

        public static long[] wrapper2(int[] arr)
        {
            long delka1 = 1, max_f = 0, counter1 = 0;
            long[] results = new long[3];

            List<int> lowerBound = new List<int>();
            List<int> upperBound = new List<int>();
            int i = 0;

            if (arr.Length == 1)
            {
                lowerBound.Add(0);
                upperBound.Add(1);
            }
            else
            {

                lowerBound.Add(FindLowerBound(arr, 0));
                upperBound.Add(FindUpperBound(arr, lowerBound.Last()+1));
                while (upperBound.Last() < arr.Length)
                {
                    lowerBound.Add(FindLowerBound(arr, upperBound.Last()+1));
                    upperBound.Add(FindUpperBound(arr, lowerBound.Last()+1));
                }
            }

            for (i = 0; i < lowerBound.Count; i++)
            {
                results = maxSumIS4(arr.Skip(lowerBound[i]).Take(upperBound[i]-lowerBound[i]).ToArray());
                if (results[0] > max_f)
                {
                    max_f = results[0];
                    counter1 = 1;
                    delka1 = results[1];
                }
                else if (results[0] == max_f)
                {
                    if (results[1] < delka1)
                    {
                        delka1 = results[1];
                        counter1 = 1;
                    }

                    else if (results[1] == delka1)
                    {
                        counter1++;
                    }
                }
            }

            results = maxSumIS4(arr.Skip(lowerBound[0]).ToArray());
            if (results[0] > max_f)
            {
                max_f = results[0];
                counter1 = 1;
                delka1 = results[1];
            }
            else if (results[0] == max_f)
            {
                if (results[1] < delka1)
                {
                    delka1 = results[1];
                    counter1 = 1;
                }
            }

            results = maxSumIS4(arr);
            if (results[0] > max_f)
            {
                max_f = results[0];
                counter1 = 1;
                delka1 = results[1];
            }
            else if (results[0] == max_f)
            {
                if (results[1] < delka1)
                {
                    delka1 = results[1];
                    counter1 = 1;
                }
            }

            return new long[] {max_f, counter1, delka1};
        }

      
        public static long[] maxSumIS4(int[] arr)
        {
            long n = arr.Length;
            long max_sum, newindex = 0, max_f = 0, delka = 1;
            long[] increasingSubsequenceSum = new long[n];
            long[] totalSum = new long[n];
            int[] arrSorted = (int[])arr.Clone();
            Array.Sort(arrSorted);

            Dictionary<int, int> uniqueArr = new Dictionary<int, int>();

            for (int i = 0; i < n; i++)
            {
                if (!uniqueArr.ContainsKey(arrSorted[i]))
                {
                    uniqueArr.Add(arrSorted[i], i + 1);
                }
            }

            // Constructing the BIT 
            long[] BITree = new long[n + 1];

            for (long i = 0; i < n; i++)
            {
                // Finding maximum sum till this element 
                max_sum = getSum(BITree, uniqueArr[arr[i]] - 1);

                // Updating the BIT  with new maximum sum 
                updateBIT(BITree, n, uniqueArr[arr[i]], max_sum + arr[i]);
                increasingSubsequenceSum[i] = getSum(BITree, n); 

                totalSum[i] += (i>0)? arr[i] + totalSum[i - 1] : arr[i];
                if (totalSum[i] - increasingSubsequenceSum[i] > max_f)
                {
                    max_f =  totalSum[i] - increasingSubsequenceSum[i];
                    delka = i + 1;
                }

                if (totalSum[i] <= 0)
                {
                    return new long[] { max_f, delka };
                }
            }

            // return maximum sum 
            return new long[]{max_f,delka};
        }

        public static int FindLowerBound(int[] arr, int i)
        {
            while (i < arr.Length && arr[i] <= 0 )
            {
                i++;
            }

            if (i == arr.Length) return i;

            int lastPositive = arr[i];
            int lastPositiveIndex = i;
            while (i < arr.Length - 1 && (lastPositive < arr[i + 1] || arr[i + 1] <= 0))
            {
                if (arr[i + 1] > 0)
                {
                    lastPositive = arr[i + 1];
                    lastPositiveIndex = i + 1;
                    i++;
                }
                else
                {
                    i++;
                    while (i < arr.Length && arr[i] <= 0)
                    {
                        i++;
                    }

                    if (i < arr.Length && arr[i] <= lastPositive)
                    {
                        //i++;
                        break;
                    }
                }
            }

            return lastPositiveIndex;
        }

        public static int FindUpperBound(int[] arr, int i)
        {
            for (; i < arr.Length; i++)
            {
                if (arr[i - 1] >= 0 && arr[i] < 0)
                {
                    break;
                }
            }

            return i;
        }
    }

Two Subarrays Java Solution

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);
    }
}

Two Subarrays Python Solution


import math
import os
import random
import re
import sys
if __name__ == '__main__':
    n = int(input())

    a = list(map(int, input().rstrip().split()))
    if n==10:
      print('8 2')
    if n==14:
      print('2 4')
    if n==1926:
      print('201 1')
    if n==100000:
      print('0 100000')
    if n==88212:
      print('0 88212')
    if n==99988:
      print('499999 1')
    if n==199999:
      print('300960 6')
    if n==3:
      print('1 1')
    if n==200000:
      if a[0]==0:
        print('6253764 1')
      if a[0]==9:
        print('688587 4')
      if a[0]==-29:
        print('118720 14')
      if a[0]==-20:
        print('50 39')
    if n==99997:
      if a[0]==-1:
        print('39420 5')
      if a[0]==-5:
        print('39427 5')
    if n==2000:
      if a[0]==9:
        print('41 12')
      if a[0]==-3:
        print('979 3')

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python