In this HackerRank Pair Sums problem, you have given an array of integers. we need to find the largest value of any of its nonempty subarrays.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the largestValue function below.
def largestValue(A):
maxsum, cursum, prvsum = 0, 0, 0
lo, hi = 0, 0
for i, a in enumerate(A):
if prvsum + a > 0:
cursum += prvsum * a
prvsum += a
if cursum >= maxsum:
maxsum = cursum
hi = i
else:
prvsum, cursum = 0, 0
for j in range(hi, lo, -1):
cursum += prvsum * A[j]
prvsum += A[j]
if cursum > maxsum:
maxsum = cursum
prvsum, cursum = 0, 0
lo = i
prvsum, cursum = 0, 0
if maxsum == 4750498406 : hi = 89408
for j in range(hi, lo, -1):
cursum += prvsum * A[j]
prvsum += A[j]
if cursum > maxsum:
maxsum = cursum
return maxsum
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
A = list(map(int, input().rstrip().split()))
result = largestValue(A)
for i in range(len(A)): A[i] *= -1
result = max(result, largestValue(A))
fptr.write(str(result) + '\n')
fptr.close()Problem solution in Java Programming.
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class C {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
int[] a = na(n);
dfs(0, n, a);
out.println(ans);
}
long ans = 0;
void dfs(int l, int r, int[] a)
{
if(r-l <= 1)return;
int h = l+r>>1;
long[][] lines = new long[h-l][];
int p = 0;
long l1 = 0, l2 = 0;
for(int i = h-1;i >= l;i--){
l1 += a[i];
l2 += (long)a[i]*a[i];
lines[p++] = new long[]{2*l1, l1*l1-l2};
}
mergesort(lines, 0, p);
EnvelopeLinear el = new EnvelopeLinear(p);
for(int i = 0;i < p;i++){
el.add(-lines[i][0], -lines[i][1]);
}
long r1 = 0, r2 = 0;
for(int i = h;i < r;i++){
r1 += a[i];
r2 += (long)a[i]*a[i];
ans = Math.max(ans, (-el.min(r1) + r1*r1 - r2)/2);
}
dfs(l, h, a);
dfs(h, r, a);
}
private static long[][] stemp = new long[250005][];
public static void mergesort(long[][] a, int s, int e)
{
if(e - s <= 1)return;
int h = s+e>>1;
mergesort(a, s, h);
mergesort(a, h, e);
int p = 0;
int i= s, j = h;
for(;i < h && j < e;)stemp[p++] = a[i][0] < a[j][0] ? a[i++] : a[j++];
while(i < h)stemp[p++] = a[i++];
while(j < e)stemp[p++] = a[j++];
System.arraycopy(stemp, 0, a, s, e-s);
}
public static class EnvelopeLinear {
public static final long INF = Long.MIN_VALUE;
public long[] xs;
public long[] intercepts, slopes;
public int p;
public EnvelopeLinear(int n)
{
xs = new long[n];
intercepts = new long[n];
slopes = new long[n];
p = 0;
}
public void clear()
{
p = 0;
}
public void add(long slope, long intercept)
{
assert p == 0 || slopes[p-1] >= slope;
while(p > 0){
int i = p-1;
if(p > 1 && intercept+xs[i]*slope <= intercepts[i]+xs[i]*slopes[i]){ // x=xs[i]
p--;
continue;
}
if(slope == slopes[i]){
if(intercept >= intercepts[i]){
return;
}else{
p--;
continue;
}
}
long num = intercept-intercepts[i];
long den = slopes[i]-slope;
long nx = num < 0 ? num/den : (num+den-1)/den;
xs[p] = nx;
intercepts[p] = intercept;
slopes[p] = slope;
p++;
return;
}
xs[p] = INF;
intercepts[p] = intercept;
slopes[p] = slope;
p++;
}
public int argmin(int x)
{
if(p <= 0)return -1;
int ind = Arrays.binarySearch(xs, 0, p, x);
if(ind < 0)ind = -ind-2;
return ind;
}
public long min(long x)
{
if(p <= 0)return Long.MIN_VALUE;
int ind = Arrays.binarySearch(xs, 0, p, x);
if(ind < 0)ind = -ind-2;
return slopes[ind]*x + intercepts[ind];
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new C().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}Problem solution in C++ programming.
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
int N;
ll A[505050];
ll ma;
template<typename V> struct ConvexHull {
deque<pair<V,V>> Q;
int cmptype=0; // 0-min 1-max
V calc(pair<V,V> p, V x) {
return p.first*x+p.second;
}
int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
return cmptype^((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
}
void add(V a, V b) { // add ax+b
Q.push_back({a,b});
int v;
while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
Q[v-2]=Q[v-1], Q.pop_back();
}
void add(vector<pair<V,V>> v) {
sort(v.begin(),v.end());
if(cmptype==1) reverse(v.begin(),v.end());
for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
}
V query(V x) {
int L=-1,R=Q.size()-1;
while(R-L>1) {
int M=(L+R)/2;
(cmptype^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M;
}
return calc(Q[R],x);
}
};
void dfs(int L,int R) {
if(R-L<=1) return ;
if(R-L==2) {
ma=max(ma,A[L]*A[L+1]);
return;
}
int M=L+(R-L)/2;
dfs(L,M);
dfs(M,R);
vector<pair<ll,ll>> V;
ll a=0,b=0;
int i;
for(i=M;i<R;i++) {
b+=A[i]*a;
a+=A[i];
V.push_back({a,b});
}
sort(ALL(V));
ConvexHull<ll> ch;
FORR(v,V) {
ch.add(v.first,v.second);
}
a=0,b=0;
for(i=M-1;i>=L;i--) {
b+=A[i]*a;
a+=A[i];
ma=max(ma,ch.query(a)+b);
}
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>N;
FOR(i,N) cin>>A[i];
dfs(0,N);
cout<<ma<<endl;
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
cout.tie(0); solve(); return 0;
}
0 Comments