FastPrepMaximum Subarray with Start and End Windows

Maximum Subarray with Start and End Windows

InMobi logoInMobi● HardNEW GRADOA
Learn

Problem statement

You are given an integer array and several queries [x1, y1, x2, y2], all using 1-based inclusive indices. For each query, choose a start index i in [x1, y1] and an end index j in [x2, y2], with i <= j.

Return the maximum sum of the contiguous subarray from i through j for every query.

Function

maximumWindowSubarraySums(values: int[], queries: int[][]) → long[]

Examples

Example 1

values = [10,-40,-30,30,40]queries = [[1,3,3,5],[2,4,3,5]]return = [40,70]

The first query chooses days 3 through 5, while the second chooses days 4 through 5.

Constraints

  • 1 <= values.length, queries.length <= 100000
  • -10^9 <= values[i] <= 10^9
  • Every query satisfies 1 <= x1 <= y1 <= values.length, 1 <= x2 <= y2 <= values.length, x1 <= x2, and y1 <= y2.

Source note: Interview prompt excerpt preserved as source evidence.

More InMobi problems

See InMobi hiring insights
public long[] maximumWindowSubarraySums(int[] values, int[][] queries) {
    // Write your code here.
}
values[10,-40,-30,30,40]
queries[[1,3,3,5],[2,4,3,5]]
expected[40,70]
Checking account…