← 返回 amazon 的题目列表Maximum Sum of Fixed-Length Subarray in a Sparse Interval Array
类型：online_judge
Problem: Maximum Sum of a Fixed-Length Subarray in a Sparse Interval Array
You are given an integer array arr of length n, but the array is represented in a compressed interval format:
Each interval [l, r, v] means every index from l to r has value v.
Indices are 1-based.
Any position not covered by an interval has value 0.
Intervals are guaranteed to be non-overlapping, and 1 <= l <= r <= n.
Return the maximum sum among all contiguous subarrays of exactly length k.
You must not expand the whole array because n can be very large.
Input Format
n m k
l1 r1 v1
l2 r2 v2
...
lm rm vm
Where:
n is the array length;
m is the number of explicitly given intervals;
k is the required subarray length;
each of the next m lines describes an interval [li, ri] with value vi.
Output Format
Print one integer: the maximum sum of any contiguous subarray of length k.
Constraints
1 <= k <= n <= 10^9
0 <= m <= 2 * 10^5
1 <= li <= ri <= n
-10^9 <= vi <= 10^9
Intervals are non-overlapping but may not be sorted.
Example 1
Input:
7 2 3
1 3 4
6 7 1
The represented array is:
[4, 4, 4, 0, 0, 1, 1]
Output:
12
Explanation: the best subarray of length 3 is [4, 4, 4], whose sum is 12.
Example
Input
7 2 3
1 3 4
6 7 1
Output
12