Frontend School

Maximum Weighted Energy Burst

DSA
hard

Maximum Weighted Energy Burst

Hard
Monotonic Stack
Prefix Sum
Arrays

Overview

In a critical energy grid, devices operate with varying power outputs. To optimize energy bursts, we need to identify contiguous segments of devices that yield the highest "weighted energy." The weighted energy of a segment is defined as the product of the sum of power outputs in that segment and the minimum power output within that same segment. This problem is crucial for dynamic resource allocation and preventing system overloads.

What you need to do / Task

Given an array powers representing the power output of N devices, your task is to find the maximum possible weighted energy burst that can be generated from any contiguous segment of devices.

Input & output

  • powers: An array of non-negative integers powers[i] representing the power output of the i-th device.
  • Return: A single integer, the maximum weighted energy burst found among all possible contiguous segments.

Clarifications

  • A segment must contain at least one device.
  • The powers array will contain at least one element.

Examples

1

Example 1

Input:

powers = [2, 1, 5, 6, 2, 3]

Output:

55

Note:

For the segment [5, 6] (indices 2 to 3), the sum is 5 + 6 = 11 and the minimum is 5. The weighted energy is 5 * 11 = 55. This is the maximum possible.

2

Example 2

Input:

powers = [10, 10, 10]

Output:

300

Note:

The entire segment [10, 10, 10] has a sum of 30 and a minimum of 10, yielding 10 * 30 = 300. This is the maximum.

3

Example 3

Input:

powers = [3, 1, 2, 4]

Output:

16

Note:

Considering each element as a potential minimum: For '1' (at index 1), the range is [3,1,2,4], sum=10, min=1, energy=10. For '2' (at index 2), the range is [2,4], sum=6, min=2, energy=12. For '4' (at index 3), the range is [4], sum=4, min=4, energy=16. The maximum is 16.

Constraints

Constraints & assumptions

  • 1 <= powers.length <= 10^5
  • 0 <= powers[i] <= 10^9
  • The maximum weighted energy can be very large. Ensure your calculations handle potential overflow if using a language with fixed-size integers (e.g., C++ long long).

What interviewers evaluate

  • Algorithmic Correctness: Identifies and correctly applies an efficient algorithm (e.g., monotonic stack with prefix sums).
  • Time & Space Complexity: Achieves optimal O(N) time complexity and O(N) space complexity.
  • Edge Cases & Robustness: Handles edge cases like single-element arrays, all identical elements, or arrays with zeros.
  • Code Quality & Readability: Writes clean, well-structured, and easy-to-understand code with appropriate variable names.

Loading editor...