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