Frontend School

Maximum Product of Subarray Sum and Minimum

DSA
hard

Maximum Product of Subarray Sum and Minimum

Hard
Monotonic Stack
Arrays
Prefix Sum

Overview

In financial data analysis, identifying segments with high value relative to a baseline is crucial. Imagine you are analyzing stock performance where nums[i] represents the daily trading volume. We're interested in finding a contiguous period (subarray) where the product of the total trading volume and the minimum daily volume within that period is maximized. This metric helps pinpoint periods of sustained high activity even when a single day might have a dip, but not too significant.

What you need to do / Task

Implement a function maxProductOfSubarraySumAndMin that takes an array of positive integers nums and returns the maximum possible value of (subarray_sum * subarray_minimum) over all non-empty contiguous subarrays.

Input & output

  • Input: nums: An array of positive integers, nums[i] representing a daily volume.
  • Output: A single bigint representing the maximum product found.

Clarifications

  • The array nums will contain only positive integers.
  • A subarray must be non-empty.
  • For any given nums[i] considered as the minimum, its associated maximal subarray [L, R] should be defined such that nums[i] is the leftmost minimum in nums[L...R] if there are ties, and nums[i] is strictly smaller than any element outside this range (nums[L-1] or nums[R+1]).

Examples

1

Example 1

Input:

nums = [2, 4, 3, 5]

Output:

36n

Note:

For nums[2]=3, the maximal subarray where 3 is the minimum is [4,3,5] (from index 1 to 3). The sum is 4+3+5=12, and the minimum is 3. The product is 12 * 3 = 36.

2

Example 2

Input:

nums = [1, 2, 3]

Output:

9n

Note:

For nums[2]=3, the maximal subarray where 3 is the minimum is [3] (from index 2 to 2). The sum is 3, and the minimum is 3. The product is 3 * 3 = 9.

3

Example 3

Input:

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

Output:

36n

Note:

For nums[1]=4, the maximal subarray where 4 is the minimum is [5,4] (from index 0 to 1). The sum is 5+4=9, and the minimum is 4. The product is 9 * 4 = 36. For nums[2]=3, the maximal subarray where 3 is the minimum is [5,4,3] (from index 0 to 2). The sum is 5+4+3=12, and the minimum is 3. The product is 12 * 3 = 36.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • The result can be very large and will exceed the capacity of a standard 32-bit or 64-bit floating-point number. You must use BigInt for calculations and the return type in JavaScript/TypeScript to avoid overflow.

What interviewers evaluate

  • Correctness: The solution correctly identifies the maximum product for all valid inputs.
  • Efficiency: The solution achieves optimal time complexity (O(N)) and reasonable space complexity (O(N)).
  • Monotonic Stack Application: Demonstrates a clear and correct application of the monotonic stack pattern to define the maximal ranges.
  • Edge Cases: Handles edge cases like single-element arrays or arrays with all identical elements.
  • Code Quality: Clean, readable, and well-structured code.

Loading editor...