FastPrepRange Maximum Subarray Sum Queries

Range Maximum Subarray Sum Queries

InMobi logoInMobi● HardNEW GRADOA
Learn

Problem statement

You are given a non-empty integer array and several range queries. Each query is a pair [left, right] using 1-based inclusive indices.

For every query, return the maximum possible sum of a non-empty contiguous subarray contained completely inside that query range.

Function

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

Examples

Example 1

values = [1,-2,3,4,-1]queries = [[1,5],[2,4],[2,2]]return = [7,7,-2]

The best sums are 3 + 4 for the first two ranges and the sole value -2 for the single-position range.

Constraints

  • 1 <= values.length <= 50000
  • -15000 <= values[i] <= 15000
  • 1 <= queries.length <= 50000
  • Every query satisfies 1 <= left <= right <= values.length.

Source note: Interview prompt excerpt preserved as source evidence.

More InMobi problems

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