Frontend School

Maximal Segment Value

DSA
medium

Maximal Segment Value

Medium
Divide and Conquer
Arrays
Segment Tree
Sparse Table
Prefix Sum

Overview

At Netflix, understanding user engagement with content segments is crucial for optimizing recommendations and content delivery. Imagine we're analyzing user interaction patterns within long-form content, where each segment has an associated "value" (e.g., watch time, sentiment score). We want to identify the most impactful contiguous segment, defined by a metric that combines its overall "strength" (sum of values) and its "quality floor" (minimum value within it). This problem challenges you to find such a segment to help us pinpoint areas of peak engagement.

What you need to do / Task

Implement the maximalSegmentValue function that takes an an array of integers nums and returns the maximum possible value of a contiguous subarray [i, j], calculated as (sum of elements from index i to j) * (minimum element from index i to j).

Your solution must adhere to a Divide and Conquer strategy and achieve optimal or near-optimal time complexity.

Input & output

Function Signature: function maximalSegmentValue(nums: number[]): number

Input:

  • nums: An array of integers, representing the values of content segments.

Output:

  • A single number representing the maximum (sum of elements in segment) * (minimum element in segment) found among all possible contiguous segments.

Clarifications

  • An empty segment is not allowed. A segment must contain at least one element.
  • The nums array will always contain at least one element.
  • The values in nums can be positive, negative, or zero.
  • The product (sum * min) can be a very large number, so ensure your language's numeric types can handle it (JavaScript's number type has sufficient precision for this problem's constraints).

Examples

1

Example 1

Input:

nums = [1, 2, 3]

Output:

10

Note:

Segments and their values:

  • [1]: sum=1, min=1 -> 1*1 = 1
  • [2]: sum=2, min=2 -> 2*2 = 4
  • [3]: sum=3, min=3 -> 3*3 = 9
  • [1,2]: sum=3, min=1 -> 3*1 = 3
  • [2,3]: sum=5, min=2 -> 5*2 = 10
  • [1,2,3]: sum=6, min=1 -> 6*1 = 6 The maximum value is 10.
2

Example 2

Input:

nums = [6, 2, 4, 3, 5]

Output:

40

Note:

The segment [6, 2, 4, 3, 5] has sum=20 and min=2, resulting in 20*2 = 40. This is the maximal value. Other notable segments: [4,3,5] (sum=12, min=3) -> 36.

3

Example 3

Input:

nums = [-1, -2, -3]

Output:

18

Note:

The segment [-1, -2, -3] has sum=-6 and min=-3, resulting in (-6)*(-3) = 18. This is the maximal value. Other notable segments: [-2,-3] (sum=-5, min=-3) -> 15. [-1] (sum=-1, min=-1) -> 1.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • The returned value can be a large number, but fits within standard 64-bit floating-point representation (e.g., JavaScript's number type).
  • Your solution should aim for an O(N log N) time complexity.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies the maximal segment value across all possible subarrays.
  • Divide and Conquer Application: Effective decomposition of the problem into subproblems and efficient combination of results.
  • Efficiency: Achieving O(N log N) time complexity and O(N log N) space complexity (or better) leveraging appropriate data structures.
  • Edge Case Handling: Correctly handles arrays with negative numbers, zeros, and single elements.

Loading editor...