Skip to content

Swiss Gondolas

Level: L4-L5 Topics: Dynamic Programming, Sliding Window, Range Queries

Problem Statement

A mountain resort has N lodges arranged in a linear chain going uphill, numbered 1 through N from bottom to top. Consecutive lodges are connected by gondolas. Each gondola (connecting lodge i to lodge i+1) has a quality rating (a star score).

You purchase a rail pass that allows you to:

  • Start at any lodge.
  • End at any lodge above your starting lodge.
  • Use at most K consecutive gondolas in a single trip.

For each possible starting lodge, find the maximum total quality rating you can achieve by riding at most K consecutive gondolas upward from that lodge.

Background & Constraints

  • There are N lodges and N-1 gondolas.
  • Gondola i connects lodge i to lodge i+1 and has quality rating q_i.
  • You ride upward only (from lower-numbered to higher-numbered lodges).
  • Starting from lodge i, you can ride gondolas i, i+1, ..., up to i+K-1 (at most K gondolas).
  • You want the contiguous sub-segment of gondolas starting at position i with length at most K that has the maximum sum.
  • 1 <= K <= N-1, and N can be up to 10^5.

Examples

Example 1:

N = 5 lodges, so N-1 = 4 gondolas
Gondola qualities: [3, 1, 4, 2]  (gondola i connects lodge i to lodge i+1)
K = 2

Starting from lodge 1: max of {[3], [3,1]} = max(3, 4) = 4
Starting from lodge 2: max of {[1], [1,4]} = max(1, 5) = 5
Starting from lodge 3: max of {[4], [4,2]} = max(4, 6) = 6
Starting from lodge 4: max of {[2]} = 2

Example 2:

N = 6 lodges, so 5 gondolas
Gondola qualities: [5, -2, 3, 8, -1]
K = 3

Starting from lodge 1: max of {[5], [5,-2], [5,-2,3]} = max(5, 3, 6) = 6
Starting from lodge 2: max of {[-2], [-2,3], [-2,3,8]} = max(-2, 1, 9) = 9
Starting from lodge 3: max of {[3], [3,8], [3,8,-1]} = max(3, 11, 10) = 11
Starting from lodge 4: max of {[8], [8,-1]} = max(8, 7) = 8
Starting from lodge 5: max of {[-1]} = -1

Hints & Common Pitfalls

  • Prefix sums make it easy to compute the sum of any contiguous sub-segment in O(1). Let prefix[0] = 0 and prefix[i] = q_1 + q_2 + ... + q_i. The sum of gondolas from i to j is prefix[j] - prefix[i-1].
  • For each starting lodge i, you need the maximum of prefix[j] - prefix[i-1] for j in [i, min(i+K-1, N-1)]. This simplifies to finding the maximum prefix[j] in a sliding window of size K.
  • Sliding window maximum can be computed in O(N) total using a monotonic deque.
  • Common mistake: Off-by-one errors with lodge indices vs. gondola indices. Lodge i starts at gondola i, and you can ride up to K gondolas.
  • Common mistake: Not considering that if all qualities are negative, the best choice might be to ride just one gondola (you must ride at least one).

Follow-Up Questions

  1. Instead of the maximum quality for each starting lodge, compute the total quality across all starting lodges (sum of the answers).
  2. What if gondola qualities can change dynamically? How would you update your answer efficiently?
  3. What if instead of consecutive gondolas, you can skip gondolas but use at most K total? How does this change the problem?
  4. What if the lodges have heights and you receive bonus points for elevation gained?
  5. What is the time and space complexity of your sliding window solution?