Katkat
Back

Maximum Sum Skyline

ExpediaSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize search spaces and use stack-based structures to maintain monotonic properties under specific geometric constraints.

Maximum Sum Skyline

You are given an array of integers heights representing the elevation of different plots of land in a city. A 'skyline' must follow a strictly non-decreasing sequence followed by a strictly non-increasing sequence (i.e., a single-peak mountain shape).

You need to find the maximum possible sum of elevations of a 'skyline' subsequence that satisfies the peak property. A subsequence must maintain the relative order of the original array, but you may choose any subset of elements. The resulting subsequence must have at least one element (which inherently forms a 'peak').

Function Signature

def max_skyline_sum(heights: List[int]) -> int:

Constraints

  • 1 <= len(heights) <= 10^5
  • 1 <= heights[i] <= 10^9

Examples

Example 1: Input: heights = [1, 5, 2, 7, 3] Output: 15 Explanation: The optimal subsequence is [1, 5, 7, 3] or [1, 2, 7, 3]. The best sum is 1+5+7+3 = 16 is not possible because it must be mountain-shaped. However, [1, 5, 7] is 13, and [5, 7, 3] is 15. The max is 15.

Example 2: Input: heights = [10, 20, 10] Output: 40 Explanation: The entire sequence is a mountain, so 10 + 20 + 10 = 40.

Edge Cases

  • A single element array: The answer is the element itself.
  • Strictly increasing or strictly decreasing arrays: The entire array can be considered a mountain peak.
  • All elements equal: The sum of all elements.

Hints

Hint 1

Consider calculating the maximum non-decreasing subsequence sum ending at each index `i` and the maximum non-increasing subsequence sum starting at each index `i`.

Hint 2

You can use dynamic programming or a Fenwick tree (Binary Indexed Tree) to efficiently calculate the maximum prefix sums in O(N log N) time.

Hint 3

For each index `i`, if you treat `heights[i]` as the peak, the total sum is `(max_increasing_sum_ending_at_i + max_decreasing_sum_starting_at_i - heights[i])`.

Follow-up questions

  • How would you modify your solution if the peak is allowed to be a plateau (a sequence of equal maximum values)?
  • What is the space complexity of your solution, and can it be reduced if we only need the total sum and not the subsequence itself?
  • How does the complexity change if the input is guaranteed to be a permutation of 1 to N?