Frontend School

Max Surge Score

DSA
medium

Max Surge Score

Medium
Monotonic Stack
Arrays

Overview

At Uber, optimizing driver earnings and passenger pricing during peak demand is crucial. Surge pricing dynamically adjusts fares to match supply and demand. Understanding historical surge patterns can help in forecasting and strategic planning. This problem asks you to analyze a sequence of daily surge multipliers to identify the most impactful "surge window" based on a specific scoring metric.

What you need to do / Task

You are given an array surgeMultipliers representing the daily surge multiplier values over a continuous period. Your task is to find the maximum possible "surge score" among all possible continuous sub-periods (subarrays) within this given period.

The "surge score" for any continuous sub-period is calculated as: minimum_multiplier_in_period * length_of_period

For example, if a sub-period has multipliers [1.5, 2.0, 1.2] and its length is 3, the minimum multiplier is 1.2. The score would be 1.2 * 3 = 3.6.

Input & output

Input:

  • surgeMultipliers: An array of numbers (number[]) representing daily surge multiplier values. Each value surgeMultipliers[i] is a positive floating-point number.

Output:

  • A single number (number) representing the maximum surge score found among all possible continuous sub-periods.

Clarifications

  • An empty surgeMultipliers array should result in a score of 0.
  • A single-element array [x] has a score of x * 1 = x.
  • The multipliers can be floating-point numbers. Ensure your calculations handle them correctly.

Examples

1

Example 1

Input:

surgeMultipliers = [1.2, 2.0, 1.5]

Output:

3.6

Note:

Consider the sub-period [1.2, 2.0, 1.5]. The minimum multiplier is 1.2 and its length is 3. The score is 1.2 * 3 = 3.6. This is the maximum score.

2

Example 2

Input:

surgeMultipliers = [2.5, 1.0, 3.0, 1.8]

Output:

4.0

Note:

Consider the sub-period [2.5, 1.0, 3.0, 1.8]. The minimum multiplier is 1.0 and its length is 4. The score is 1.0 * 4 = 4.0. This is the maximum score.

3

Example 3

Input:

surgeMultipliers = [1.0, 1.0, 1.0]

Output:

3.0

Note:

For the entire period [1.0, 1.0, 1.0], the minimum multiplier is 1.0 and its length is 3. The score is 1.0 * 3 = 3.0.

Constraints

Constraints & assumptions

  • 1 <= surgeMultipliers.length <= 10^5
  • 1.0 <= surgeMultipliers[i] <= 5.0 (Multipliers are positive and within a typical range)
  • The input array will only contain valid numbers.

What interviewers evaluate

  • Problem Understanding & Edge Cases: Ability to correctly interpret the problem statement and handle edge cases (e.g., empty array, single element).
  • Algorithmic Approach: Developing an efficient algorithm, specifically leveraging a monotonic stack for optimal time complexity.
  • Code Correctness & Readability: Writing clean, correct, and well-structured code.
  • Time and Space Complexity: Analyzing and optimizing the solution's performance.

Loading editor...