Algorithm


Problem Name: Data Structures - Pair Sums

Problem Link: https://www.hackerrank.com/challenges/pair-sums/problem?isFullScreen=true

In this HackerRank in Data Structures - Pair Sums solutions

Given an array, we define its value to be the value obtained by following these instructions:

 

  • Write down all pairs of numbers from this array.
  • Compute the product of each pair.
  • Find the sum of all the products.

For example, for a given array, for a given array [7,2, -1, 2],

Pairs (7, 2), (7, -1), (7, 2), (2, -1), (2, 2), (-1, 2)
Products of the pairs 14, -7, 14, -2, 4, -2
Sum of the products 14 + (-7) + 14 + (-2) + 4 + (-2) = 21

Note that (7, 2) is listed twice, one for each occurrence of 2.

Given an array of integers, find the largest value of any of its nonempty subarrays.

 

Note: A subarray is a contiguous subsequence of the array.

 

Complete the function largestValue which takes an array and returns an integer denoting the largest value of any of the array's nonempty subarrays.

Input Format

The first line contains a single integer n, denoting the number of integers in array A.

The second line contains n space-separated integers Ai denoting the elements of array A.

Constraints

  • 3 <= n <= 5 * 10**5
  • -10**3 <= Ai <= 10**3

Subtasks

  • n <= 5000 for 20% of the points.
  • n <= 2 * 10**5 for 70% of the points.

Output Format

Print a single line containing a single integer denoting the largest value of any of the array's nonempty subarrays.

Sample Input 0

6
-3 7 -2 3 5 -2

Sample Output 0

41

Explanation 0

In this case, we have A = [-3,7,-2,3,5,-2]. The largest-valued subarray turns out to be [7,-2,3,5] with value

(7 * -2) + (7 * 3) + (7 * 5) + (-2 * 3) + (-2 * 5) + (3 * 5) = 41

Sample Input 1

10
5 7 -5 6 3 9 -8 2 -1 10

Sample Output 1

200

 

 

 

 

 

 

Code Examples

#1 Code Example with C++ Programming

Code - 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 p, V x) {
        return p.first*x+p.second;
    }
    int dodo(pair A,pair B, pair 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 < pairfirst,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;
    
    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;
}
Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - 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)>; }
}
Copy The Code & Try With Live Editor

#3 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'largestValue' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY A as parameter.
#

from itertools import combinations as cb
def largestValue(A):
    maximum = float('-inf')
    length = len(A)
    
    for i in range(length):
        for n in range(length-1, i,-1):
            stemp = sum([sx*sy for sx, sy in cb(A[i:n], 2)])
            if stemp > maximum:
                maximum = stemp
    
    return maximum

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    A = list(map(int, input().rstrip().split()))

    result = largestValue(A)

    fptr.write(str(result) + '\n')

    fptr.close()

Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Fibonacci Numbers Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Functional Palindromes solution in Hackerrank - Hacerrank solution C, C++, java,js, Python