Algorithm


Problem Name: Data Structures - The Strange Function

Problem Link: https://www.hackerrank.com/challenges/the-strange-function/problem?isFullScreen=true

In this HackerRank in Data Structures - The Strange Function solutions

One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development.

You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting of n integers a1,a2, ... , an.

For example, for an input array [ 10, -5, 5, 20 ], a subsegment f(1,1) would be computed as follows:

image

What is max   f(1,1) , i.e., the maximum value of f(1,1) among all subsegments (l,r)?

             1 <= l <= r <= n

Complete the function maximumValue which takes an integer array as input and returns the maximum value of f among all subsegments (l,r).

Input Format

The first line contains a single integer n

The second line contains n space-separated integers a1,a2, ... ,an

Constraints

1 <= n <= 50000

-10**6 <=  ai <= 10**6

Output Format

Print a single integer denoting the answer

Sample Input 0

4
10 -5 5 20

Sample Output 0

50

Explanation 0

The maximum value occurs at f(1,4) = 50 as shown below.

image

Sample Input 1

5
7 12 24 6 5

Sample Output 1

144

Explanation 1

The maximum value occurs at f(2,3) = 144

 

 

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INF 200000
typedef struct _node
{
    int gcd;
    int max;
    long long sum;
}node;
typedef struct _tree_node
{
    enum
    {
        red, black
    }colour;
    int data;
    int real;
    struct _tree_node *left, *right, *parent;
}tree_node;
int a[50000], b[50000], nonzero[50000], rp[30], rc[30], treei[200000], rs, s, N;
long long ans, p[1000], tree[200000];
node t[200000];
tree_node *map[50000];
void getp(long long N, long long *prim)
{
    long long i, j, index = 2, flag;
    if( N <= 1 )
    {
        prim[0] = 0;
        return;
    }
    if( N == 2 )
    {
        prim[0] = 2;
        prim[1] = 0;
        return;
    }
    prim[0] = 2;
    prim[1] = 3;
    for( i = 5 ; i  < = N ; i += 2 )
    {
        for( j = 1, flag = 1 ; prim[j]  < = sqrt(i) ; j++ )
        {
            if( i % prim[j] == 0 )
            {
                flag = 0;
                break;
            }
        }
        if( flag == 1 )
        {
            prim[index] = i;
            index++;
        }
    }
    prim[index] = 0;
    return;
}
long long CC(long long n, long long d)
{
    if( n == 0 )
    {
        return d;
    }
    if( d == 0 )
    {
        return n;
    }
    while(1)
    {
        n = n % d;
        if( n == 0 )
        {
            return d;
        }
        d = d % n;
        if( d == 0 )
        {
            return n;
        }
    }
}
int max(int x, int y>
{
    return ( x > y ) ? x : y;
}
int min(int x, int y)
{
    return ( x  <  y ) ? x : y;
}
int abss(int x)
{
    return ( x < 0 ) ? -x : x;
}
int search(tree_node *root, int data)
{
    if(!root)
    {
        return INF;
    }
    if( root -> data == data )
    {
        return root -> real;
    }
    if( data  <  root -> data )
    {
        return search(root -> left, data);
    }
    return search(root -> right, data);
}
void left_rotate(tree_node **root, tree_node *x)
{
    tree_node *y;
    y = x -> right;
    if(!y)
    {
        return;
    }
    x -> right = y -> left;
    if(y -> left)
    {
        y -> left -> parent = x;
    }
    y -> parent = x -> parent;
    if( x -> parent == NULL )
    {
        *root = y;
    }
    else if( x == x -> parent -> left )
    {
        x -> parent -> left = y;
    }
    else
    {
        x -> parent -> right = y;
    }
    y -> left = x;
    x -> parent = y;
    return;
}
void right_rotate(tree_node **root, tree_node *y)
{
    tree_node *x;
    x = y -> left;
    if(!x)
    {
        return;
    }
    y -> left = x -> right;
    if(x -> right)
    {
        x -> right -> parent = y;
    }
    x -> parent = y -> parent;
    if( y -> parent == NULL )
    {
        *root = x;
    }
    else if( y == y -> parent -> right )
    {
        y -> parent -> right = x;
    }
    else
    {
        y -> parent -> left = x;
    }
    x -> right = y;
    y -> parent = x;
    return;
}
void reconstruct(tree_node **root, tree_node *x)
{
    tree_node *y, *z;
    y = x -> parent;
    z = x -> parent -> parent;
    x -> colour = black;
    z -> colour = red;
    x -> parent = z -> parent;
    if( z -> parent == NULL )
    {
        *root = x;
    }
    else if( z == z -> parent -> left )
    {
        z -> parent -> left = x;
    }
    else
    {
        z -> parent -> right = x;
    }
    if( z -> left == y )
    {
        x -> left = y;
        x -> right = z;
    }
    else
    {
        x -> left = z;
        x -> right = y;
    }
    y -> parent = z -> parent = x;
    y -> left = y -> right = z -> left = z -> right = NULL;
    return;
}
int normal_insert(tree_node **root, tree_node *x)
{
    if( *root == NULL )
    {
        *root = x;
    }
    else if( (*root) -> data == x -> data )
    {
        return 0;
    }
    else
    {
        x -> parent = *root;
        if( (*root) -> data > x -> data )
        {
            return normal_insert(&((*root) -> left), x);
        }
        else
        {
            return normal_insert(&((*root) -> right), x);
        }
    }
    return 1;
}
void insert(tree_node **root, tree_node *x)
{
    if(!normal_insert(root, x))
    {
        return;
    }
    tree_node *y;
    x -> colour = red;
    while( x != *root && x -> parent -> colour == red )
    {
        if( x -> parent == x -> parent -> parent -> left )
        {
            y = x -> parent -> parent -> right;
            if(!y)
                if( x == x -> parent -> left )
                {
                    x -> parent -> colour = black;
                    x -> parent -> parent -> colour = red;
                    right_rotate(root, x -> parent -> parent);
                }
                else
                {
                    y = x -> parent;
                    reconstruct(root, x);
                    x = y;
                }
            else if( y -> colour == red )
            {
                x -> parent -> colour = black;
                y -> colour = black;
                x -> parent -> parent -> colour = red;
                x = x -> parent -> parent;
            }
            else
            {
                if( x == x -> parent -> right )
                {
                    x = x -> parent;
                    left_rotate(root, x);
                }
                x -> parent -> colour = black;
                x -> parent -> parent -> colour = red;
                right_rotate(root, x -> parent -> parent);
            }
        }
        else
        {
            y = x -> parent -> parent -> left;
            if(!y)
                if( x == x -> parent -> right )
                {
                    x -> parent -> colour = black;
                    x -> parent -> parent -> colour = red;
                    left_rotate(root, x -> parent -> parent);
                }
                else
                {
                    y = x -> parent;
                    reconstruct(root, x);
                    x = y;
                }
            else if( y -> colour == red )
            {
                x -> parent -> colour = black;
                y -> colour = black;
                x -> parent -> parent -> colour = red;
                x = x -> parent -> parent;
            }
            else
            {
                if( x == x -> parent -> left )
                {
                    x = x -> parent;
                    right_rotate(root, x);
                }
                x -> parent -> colour = black;
                x -> parent -> parent -> colour = red;
                left_rotate(root, x -> parent -> parent);
            }
        }
    }
    (*root) -> colour = black;
    return;
}
void merge(int *a, int *left, int *right, int left_size, int right_size, int *new_size)
{
    int i = 0, j = 0, index = 0;
    while( i < left_size || j  <  right_size )
    {
        if( i == left_size )
        {
            a[index++] = right[j];
            j++;
        }
        else if( j == right_size )
        {
            a[index++] = left[i];
            i++;
        }
        else if( left[i]  < = right[j] >
        {
            a[index++] = left[i];
            i++;
        }
        else
        {
            a[index++] = right[j];
            j++;
        }
        if( index > 1 && a[index-2] == a[index-1] )
        {
            index--;
        }
    }
    (*new_size) = index;
    return;
}
void init(int n)
{
    N = 1;
    while( N < n )
    {
        N *= 2;
    }
    for( int i = 1 ; i  <  N + n ; i++ )
    {
        tree[i] = -1000000000000000000LL;
    }
}
int range_sum(int i, int j)
{
    int ansi;
    long long ans = -1000000000000000000LL;
    for( i += N, j += N ; i  < = j ; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
    {
        if( i % 2 == 1 >
            if( tree[i] > ans )
            {
                ans = tree[i];
                ansi = treei[i];
            }
        if( j % 2 == 0 )
            if( tree[j] > ans )
            {
                ans = tree[j];
                ansi = treei[j];
            }
    }
    return ansi;
}
void update(int i, long long val)
{
    int j;
    for( j = i + N ; j ; j /= 2 )
        if( val > tree[j] )
        {
            tree[j] = val;
            treei[j] = i;
        }
}
void sort_a(int *a, int size, int *new_size)
{
    if( size < 2 )
    {
        (*new_size) = size;
        return;
    }
    int m = ( size + 1 ) / 2, i;
    int *left, *right;
    left = (int*)malloc(m * sizeof(int));
    right = (int*)malloc(( size - m ) * sizeof(int));
    for( i = 0 ; i  <  m ; i++ )
    {
        left[i] = a[i];
    }
    for( i = 0 ; i  <  size - m ; i++ )
    {
        right[i] = a[i+m];
    }
    int new_l_size = 0, new_r_size = 0;
    sort_a(left, m, &new_l_size);
    sort_a(right, size-m, &new_r_size);
    merge(a, left, right, new_l_size, new_r_size, new_size);
    free(left);
    free(right);
    return;
}
long long query(int v, int tl, int tr, int l, int r, int *gcd, int *ma, long long *sum>
{
    int tm, g1, g2, m1, m2;
    long long s1, s2;
    if( tl > r || tr < l >
    {
        *gcd = 0;
        *ma = 0;
        *sum = 0;
        return 0;
    }
    if( tl >= l && tr <= r )
    {
        *gcd = t[v].gcd;
        *ma = t[v].max;
        *sum = t[v].sum;
        return (*gcd) * ( (*sum) - (*ma) );
    }
    tm = ( tl + tr ) / 2;
    query(2*v, tl, tm, l, r, &g1, &m1, &s1);
    query(2*v+1, tm+1, tr, l, r, &g2, &m2, &s2);
    *gcd = CC(g1, g2);
    *ma = max(m1, m2);
    *sum = s1 + s2;
    return (*gcd) * ( (*sum) - (*ma) );
}
void solve(int start, int bs, int ns)
{
    int gcd, ma, i, j;
    long long t, sum;
    for( i = 0 ; i  <  bs ; i++ )
    {
        if( b[i] == ns )
        {
            continue;
        }
        if( i == bs - 1 )
        {
            j = range_sum(b[i], ns-1);
        }
        else
        {
            j = range_sum(b[i], b[i+1]-1);
        }
        t = query(1, 0, ns-1, start, j, &gcd, &ma, &sum>;
        if( t > ans )
        {
            ans = t;
        }
    }
    return;
}
void copy_tree(tree_node **d, tree_node *r)
{
    tree_node *p;
    if(!r)
    {
        return;
    }
    copy_tree(d, r->left);
    p = (tree_node*)malloc(sizeof(tree_node));
    p -> data = r -> data;
    p -> real = r -> real;
    p -> left = p -> right = p -> parent = NULL;
    insert(d, p);
    b[s++] = r -> real + 1;
    copy_tree(d, r -> right);
    return;
}
void build(int v, int tl, int tr)
{
    int tm;
    if( tl == tr )
    {
        t[v].gcd = abss(a[tl]);
        t[v].max = t[v].sum = a[tl];
    }
    else
    {
        tm = ( tl + tr ) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        t[v].gcd = CC(t[2*v].gcd, t[2*v+1].gcd);
        t[v].max = max(t[2*v].max, t[2*v+1].max);
        t[v].sum = t[2*v].sum + t[2*v+1].sum;
    }
    return;
}
int main()
{
    int n, x, ns, i, j, k, l;
    long long sum;
    tree_node *last_node, *p_node;
    getp(1000, p);
    scanf("%d", &n);
    for( i = 0 ; i < n ; i++ )
    {
        scanf("%d", a + i);
    }
    build(1, 0, n-1);
    init(n);
    for( i = sum = 0 ; i  <  n ; i++ )
    {
        sum += a[i];
        update(i, sum>;
    }
    for( i = n - 1 ; i >= 0 ; i-- )
    {
        if( i == n - 1 )
        {
            last_node = NULL;
        }
        else
        {
            last_node = map[i+1];
        }
        if(a[i])
        {
            nonzero[i] = i;
            for( j = rs = 0, x = abss(a[i]) ; p[j] && p[j] * p[j] <= x ; j++ )
            {
                if( x % p[j] == 0 )
                {
                    rp[rs] = p[j];
                    rc[rs] = 0;
                    while( x % p[j] == 0 )
                    {
                        rc[rs]++;
                        x /= p[j];
                    }
                    rs++;
                }
            }
            if( x != 1 )
            {
                rp[rs] = x;
                rc[rs] = 1;
                rs++;
            }
            for( j = s = 0 ; j  <  rs ; j++ )
            {
                for( k = 0, x = rp[j] ; k  <  rc[j] ; k++, x *= rp[j] )
                {
                    p_node = (tree_node*)malloc(sizeof(tree_node)>;
                    p_node -> data = x;
                    p_node -> left = p_node -> right = p_node -> parent = NULL;
                    l = search(last_node, x);
                    if( l != INF )
                    {
                        p_node -> real = l;
                        b[s++] = l + 1;
                    }
                    else
                    {
                        p_node -> real = i;
                    }
                    insert(&map[i], p_node);
                }
            }
            b[s++] = i;
            sort_a(b, s, &ns);
            solve(i, ns, n);
        }
        else
        {
            nonzero[i] = INF;
            s = 0;
            copy_tree(&map[i], last_node);
            if( i != n - 1 && nonzero[i+1] != INF )
            {
                b[s++] = nonzero[i+1];
            }
            sort_a(b, s, &ns);
            solve(i, ns, n);
        }
        if( i != n - 1 )
        {
            nonzero[i] = min(nonzero[i], nonzero[i+1]);
        }
    }
    printf("%lld", ans);
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i  <  (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int> pi;
typedef vector<int> vi;
typedef vector < pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template < class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val))  <  0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x  <  -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

template < class T> struct MINRMQ {
    int n;
    vector<T> a;
    vector < vector<T> > f;

    T best(T a, T b) {
        return min(a, b);
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p)  <  n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i  <  (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i  <  n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l)  <  n; l++) {
            for (int i = 0; i + k  <  n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
template < class T> struct MAXRMQ {
    int n;
    vector<T> a;
    vector < vector<T> > f;

    T best(T a, T b) {
        return max(a, b);
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p)  <  n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i  <  (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i  <  n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l)  <  n; l++) {
            for (int i = 0; i + k  <  n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
template < class T> struct GCDRMQ {
    int n;
    vector<T> a;
    vector < vector<T> > f;

    T best(T a, T b) {
        return __gcd(abs(a), abs(b));
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p)  <  n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i  <  (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i  <  n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l)  <  n; l++) {
            for (int i = 0; i + k  <  n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
MINRMQ < long long> minrmq;
MAXRMQ maxrmq;
GCDRMQ < int> gcdrmq;

const int maxn = 1e6 + 5;
int n;
long long a[maxn];
long long b[maxn];
int l[maxn];
int r[maxn];

int getnext(int i, int u, int v) {
    int g = gcdrmq.query(u, v);
    int lo = v, hi = r[i];
    while (lo  <  hi) {
        int mi = lo + hi + 1 >> 1;
        if (gcdrmq.query(u, mi) == g) {
            lo = mi;
        }
        else {
            hi = mi - 1;
        }
    }
    return lo + hi >> 1;
}
int getprev(int i, int u, int v) {
    int g = gcdrmq.query(u, v);
    int lo = l[i], hi = u;
    while (lo  <  hi) {
        int mi = lo + hi >> 1;
        if (gcdrmq.query(mi, v) != g) {
            lo = mi + 1;
        }
        else {
            hi = mi;
        }
    }
    return lo + hi >> 1;
}

long long query1(int i, int u, int x, int y) {
    return gcdrmq.query(u, x) * (maxrmq.query(x, y) - b[u - 1] - a[i]);
}

long long query2(int i, int x, int y, int u) {
    return gcdrmq.query(y, u) * (b[u] - minrmq.query(x - 1, y - 1) - a[i]);
}

long long ff(int i, int u, int v) {
    return gcdrmq.query(u, v) * (b[v] - b[u - 1] - a[i]);
}

void solve() {
    cin >> n;
    FOR(i, 1, n + 1) cin >> a[i];
    partial_sum(a, a + n + 1, b);
    minrmq.init(n + 1);
    maxrmq.init(n + 1);
    gcdrmq.init(n + 1);
    FOR(i, 1, n + 1) minrmq.upd(i, b[i]);
    FOR(i, 1, n + 1) maxrmq.upd(i, b[i]);
    FOR(i, 1, n + 1) gcdrmq.upd(i, a[i]);
    minrmq.build();
    maxrmq.build();
    gcdrmq.build();
    FOR(i, 1, n + 1) l[i] = r[i] = i;
    FOR(i, 2, n + 1) {
        int ptr = i;
        while (ptr > 1 && a[i] >= a[ptr - 1]) ptr = l[ptr - 1];
        l[i] = ptr;
    }
    FORd(i, n, 1) {
        int ptr = i;
        while (ptr  <  n && a[i] > a[ptr + 1]) ptr = r[ptr + 1];
        r[i] = ptr;
    }
    long long res = -8 * LINF;
    FOR(i, 1, n + 1) {
        if (i - l[i]  <  r[i] - i) {
            FORd(j, i + 1, l[i]) {
                int ptr = i;
                while (ptr <= r[i]) {
                    int nptr = getnext(i, j, ptr);
                    chkmax(res, query1(i, j, ptr, nptr));
                    ptr = nptr + 1;
                }
            }
        }
        else {
            FOR(j, i, r[i] + 1) {
                int ptr = i;
                while (ptr >= l[i]) {
                    int nptr = getprev(i, ptr, j);
                    chkmax(res, query2(i, nptr, ptr, j));
                    ptr = nptr - 1;
                }
            }
        }
    }
    cout << res << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.TreeMap;

public class Solution98 {
    static final Scanner scanner = new Scanner(System.in);
    static class Segment {
        int left, right, val;
        Segment(int left, int right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }
    private static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x % y);
    }

    public static void main(String[] args) {
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i  <  n; i++) {
            a[i] = scanner.nextInt();
        }

        long ans = 0;
        long sum = 0;
        TreeMap < Integer, Integer> tmap = new TreeMap<>();
        SegmentTree tree = new SegmentTree(n);
        Deque < Segment> dq = new ArrayDeque<>();
        for (int i = 0; i  <  n; i++) {
            TreeMap segmentTree = new TreeMap<>();
            for (int j : tmap.keySet()) {
                int k = gcd(j, Math.abs(a[i]));
                int idx = tmap.get(j);
                if (segmentTree.containsKey(k)) {
                    int cur = segmentTree.get(k);
                    segmentTree.put(k, Math.min(idx, cur));
                } else {
                    segmentTree.put(k, idx);
                }
            }
            if (segmentTree.containsKey(Math.abs(a[i]))) {
                int j = segmentTree.get(Math.abs(a[i]));
                segmentTree.put(Math.abs(a[i]), Math.min(i, j));
            } else {
                segmentTree.put(Math.abs(a[i]), i);
            }
            tmap = segmentTree;
            tree.add(i, i, sum);

            Segment s = new Segment(i, i, a[i]);
            while (!dq.isEmpty() && dq.getLast().val  < = a[i]) {
                tree.add(dq.getLast().left, dq.getLast().right, -dq.getLast().val);
                s.left = dq.getLast().left;
                dq.removeLast();
            }
            tree.add(s.left, s.right, s.val);
            dq.addLast(s);
            sum += a[i];
            for (int j : tmap.keySet()) {
                int pos = tmap.get(j);
                ans = Math.max(ans, j * (sum - tree.get(pos, i)));
            }
        }

        System.out.println(ans);
    }
}

class SegmentTree {
    private int n;
    private long[] min, add;

    SegmentTree(int size) {
        n = 1;
        while (n  <  size) {
            n *= 2;
        }
        min = new long[2 * n];
        add = new long[2 * n];
    }

    private void clear(int i, int l, int r) {
        min[i] = 0;
        add[i] = 0;
        if (l == r - 1) {
            return;
        }
        int tm = (l + r) / 2;
        clear(2 * i + 1, l, tm);
        clear(2 * i + 2, tm, r);
    }

    void clear(int n) {
        this.n = n;
        clear(0, 0, n);
    }

    private void push(int i, int tl, int tr) {
        min[i] += add[i];
        if (tl != tr - 1) {
            add[2 * i + 1] += add[i];
            add[2 * i + 2] += add[i];
        }
        add[i] = 0;
    }

    private void add(int i, int lt, int rt, int l, int r, long diff) {
        push(i, lt, rt);
        if (l >= rt || r  < = lt) {
            return;
        }

        if (l <= lt && rt <= r) {
            add[i] += diff;
            push(i, lt, rt);
            return;
        }

        int tm = (lt + rt) / 2;
        add(2 * i + 1, lt, tm, l, r, diff);
        add(2 * i + 2, tm, rt, l, r, diff);
        min[i] = Math.min(min[2 * i + 1], min[2 * i + 2]);
    }

    private long get(int i, int lt, int rt, int l, int r) {
        push(i, lt, rt);
        if (l >= rt || r  < = lt) {
            return Long.MAX_VALUE;
        }

        if (l <= lt && rt <= r) {
            return min[i];
        }

        int tm = (lt + rt) / 2;
        return Math.min(get(2 * i + 1, lt, tm, l, r), get(2 * i + 2, tm, rt, l, r));
    }

    void add(int l, int r, long diff) {
        add(0, 0, n, l, r + 1, diff);
    }

    long get(int l, int r) {
        return get(0, 0, n, l, r + 1);
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


from math import gcd

def parseInput(f):
    return [f(x) for x in input().split()]

n=int(input())
array=parseInput(int)
stack=[]
answer=float('-inf')
for number in array:
    for i in range(len(stack)):
        stack[i][0]=gcd(abs(stack[i][0]),abs(number))
        stack[i][1]+=number
        if number > stack[i][2]:
            stack[i][1]-=number-stack[i][2]
            stack[i][2]=number

    stack.append([number,0,number])
    newStack=[]
    for i in range(len(stack)):
        if newStack and newStack[-1][0] == stack[i][0]:
            if newStack[-1][1] <= stack[i][1]:
                if newStack[-1][1]+newStack[-1][2] > stack[i][1]+stack[i][2]:
                    newStack.append(stack[i])
                    continue
                newStack[-1][1]=stack[i][1]
                newStack[-1][2]=stack[i][2]
        else:
            newStack.append(stack[i])
    stack = newStack[:]
    answer=max(answer,max(abs(stack[i][0])*stack[i][1] for i in range(len(stack))))
print(answer)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Costly Intervals solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Self-Driving Bus solution in Hackerrank - Hacerrank solution C, C++, java,js, Python