In this HackerRank The Strange Function problem you need to complete the function maximumValue which takes an integer array as input and returns the maximum value of f among all subsegments [l,r].
Problem solution in 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)
Problem solution in 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<Integer, Integer> 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); } }
Problem solution in 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<class T> 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<long long> 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 << "msn"; return 0; }
Problem solution in 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; }