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.
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')
