Question - 4

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:

Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.

Given M queries, your program must output the results of these queries.

class Solution {
    static class Pair {
        int sum, mSum, bps, bss;

        // mSum -> max sum, bps -> best prefix sum, bss -> best suffix sum
        Pair(int s, int m, int bps, int bss) {
            this.sum = s;
            this.mSum = m;
            this.bps = bps;
            this.bss = bss;
        }
    }

    public static void buildTree(int[] arr, Pair[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], arr[start], arr[start], arr[start]);
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, tree, start, mid, 2 * index);
        buildTree(arr, tree, mid + 1, end, 2 * index + 1);
        tree[index] = new Pair(0, 0, 0, 0);
        tree[index].sum = tree[2 * index].sum + tree[2 * index + 1].sum;
        tree[index].mSum = Math.max(Math.max(tree[2 * index].mSum, tree[2 * index + 1].mSum),
                Math.max(
                        Math.max(tree[2 * index].sum + tree[2 * index + 1].bps,
                                tree[2 * index].bss + tree[2 * index + 1].sum),
                        tree[2 * index].bss + tree[2 * index + 1].bps));
        tree[index].bps = Math.max(tree[2 * index].bps, tree[2 * index].sum + tree[2 * index + 1].bps);
        tree[index].bss = Math.max(tree[2 * index + 1].bss, tree[2 * index].bss + tree[2 * index + 1].sum);
    }

    public static Pair findMaxProd(Pair[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(-1000000, -1000000, -1000000, -1000000);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair leftPair = findMaxProd(tree, start, mid, 2 * index, L, R);
        Pair rightPair = findMaxProd(tree, mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(0, 0, 0, 0);
        ans.sum = leftPair.sum + rightPair.sum;
        ans.mSum = Math.max(Math.max(leftPair.mSum, rightPair.mSum), Math.max(
                Math.max(leftPair.sum + rightPair.bps, leftPair.bss + rightPair.sum), leftPair.bss + rightPair.bps));
        ans.bps = Math.max(leftPair.bps, leftPair.sum + rightPair.bps);
        ans.bss = Math.max(leftPair.bss + rightPair.sum, rightPair.bss);
        return ans;
    }

    public static void rangeQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        Pair tree[] = new Pair[4 * n];
        buildTree(arr, tree, 0, n - 1, 1);
        for (int[] query : queries) {
            System.out.println(findMaxProd(tree, 0, n - 1, 1, query[1], query[2]).mSum);
        }
    }
}