Question

De-Shaw | OA Coding Questions and Solutions | Set - 14 | 2022

Answer 1

Given an array arr of size n find the maximum value of
sum[i....j] X arr[k] where i<=k<=j
1<=n<=5 X 10^5
-10^6 <= arr[i] <= 10^6

Answer 2

take two arrays left and right of size n
left[i] will store maximum sum of subarray ending at i from start
right[i] will store maximum sum of subarray ending at i from end
ans=max(ans,(left[i]+right[i]-arr[i])*arr[i])

similarly store min sum for negative elements

will this approach work??

Answer 3

I appeared for the test. Was able to solve all the test cases using Kadane's algorithm. The thing to notice is that the max value can be achieved by multiplying (Maximum Sum Subarray)(Maximum element of that subarray) OR (Minimum Sum Subarray)(Minimum element of that subarray). The second case is because multiplying two negative values produces a positive value. This can be achieved in O(N) by Kadane's algo. Below is the code which passed all 15 test cases.

`

public static long maxStock(List<Integer> stockValue) {
    int n=stockValue.size();
    int[] arr = new int[n];
    int i=0;
    for(int x:stockValue) {
        arr[i]=x;
        i++;
    }
   
    return Math.max(maxSubArraySum(arr),minSubArraySum(arr));
}

     static long maxSubArraySum(int a[]) {
    long size = a.length;
    long max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
    long maxE = Integer.MIN_VALUE;
    long ansMax = Integer.MIN_VALUE;
    for (int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        maxE = Math.max(maxE, a[i]);
        if (max_so_far < max_ending_here) {
            max_so_far = max_ending_here;
            ansMax = Math.max(ansMax, max_so_far * maxE);
        }
        if (max_ending_here < 0) {
            max_ending_here = 0;
            maxE = Integer.MIN_VALUE;
        }
    }

    return ansMax;
}

static long minSubArraySum(int a[]) {
    long size = a.length;
    long min_so_far = Integer.MAX_VALUE, min_ending_here = 0;
    long minE = Integer.MAX_VALUE;
    long ansMin = Integer.MIN_VALUE;
    for (int i = 0; i < size; i++) {
        min_ending_here = min_ending_here + a[i];
        minE = Math.min(minE, a[i]);
        if (min_so_far > min_ending_here) {
            min_so_far = min_ending_here;
            ansMin = Math.max(ansMin, min_so_far * minE);
        }
        if (min_ending_here > 0) {
            min_ending_here = 0;
            minE = Integer.MAX_VALUE;
        }
    }

    return ansMin;
}