Find a Maximum-Sum Window in a Sparse Array

Problem Statement

You are given a sparse array represented as a list of segments, where each segment is defined by a (value, length) tuple. For example, [(10, 3), (5, 2)] represents the array [10, 10, 10, 5, 5].

Given this compressed representation and an integer k, find the maximum sum of any contiguous subarray of length k. The total length of the original array can be up to 10^15, but the number of segments will not exceed 10^5.

Function Signature

def max_window_sum(segments, k):
    # segments: List of tuples (value, length)
    # k: int
    pass

Constraints

• Total array length N <= 10^15
• Number of segments M <= 10^5
• 1 <= k <= N

Examples

Example 1: Input: segments = [(1, 2), (3, 4), (2, 1)], k = 3 Array representation: [1, 1, 3, 3, 3, 3, 2] Windows of length 3: [1,1,3]=5, [1,3,3]=7, [3,3,3]=9, [3,3,3]=9, [3,3,2]=8 Output: 9

Example 2: Input: segments = [(10, 100), (20, 100)], k = 150 Output: 2500 (50 elements of 10 + 100 elements of 20)

Edge Cases

• k is equal to the length of a single segment.
• k spans multiple segments.
• All values in the segments are negative.