Busiest stock window
A warehouse logs the net change in stock every hour: deliveries make it positive, shipments make it negative. The planner wants to know which stretch of K consecutive hours saw the largest total net change. Read N and K, then the N hourly values, and print the starting hour (0-based) of the best window and its total, separated by a space. If several windows tie for the largest total, print the earliest starting hour. N can be large, so the solution must not recompute each window's sum from scratch.
Input
The first line has N and K separated by a space. The second line has N integers separated by spaces.
Output
One line: <start> <total>.
Example 1
Input
8 3 4 -2 7 1 -5 3 6 -1
Output
0 9
The windows of length 3 have totals 9, 6, 3, -1, 4 and 8; the largest is 9, starting at hour 0.
Example 2
Input
5 5 -1 -2 -3 -4 -5
Output
0 -15
When K equals N there is only one window, even though its total is negative.
Constraints
- 1 <= K <= N <= 200000
- -1000000 <= each value <= 1000000
- Use i64 for the totals
Hints
Hint 1 of 3
Summing each window separately costs O(N * K). Two neighbouring windows share K - 1 values, so their sums differ by one value entering and one leaving.
Hint 2 of 3
Compute the first window's sum, then for each new start add values[start + k - 1] and subtract values[start - 1].
Hint 3 of 3
Only replace the best window when the new sum is strictly greater, so the earliest start is kept on ties. The same answer can be computed with a prefix-sum array as prefix[i + k] - prefix[i].
Solution
Show a reference solution and explanation
use std::io::{self, BufRead};
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let header = lines.next().unwrap().unwrap();
let mut header = header.split_whitespace().map(|x| x.parse::<usize>().unwrap());
let n = header.next().unwrap();
let k = header.next().unwrap();
let values: Vec<i64> = lines
.next()
.unwrap()
.unwrap()
.split_whitespace()
.map(|x| x.parse().unwrap())
.collect();
let mut window: i64 = values[..k].iter().sum();
let mut best_sum = window;
let mut best_start = 0;
for start in 1..=(n - k) {
window += values[start + k - 1] - values[start - 1];
if window > best_sum {
best_sum = window;
best_start = start;
}
}
println!("{} {}", best_start, best_sum);
}
Why it works
The sliding-window idea is that consecutive windows overlap almost entirely, so moving the window one step to the right changes its sum by exactly one entering value minus one leaving value. That turns O(N * K) work into O(N): one pass to sum the first window and one pass over the remaining starts. The tie rule falls out of the comparison operator: > keeps the earliest maximum, >= would keep the latest. Totals need i64 because 200000 values of magnitude 1000000 can reach 2 * 10^11, far beyond i32. The slice expression values[..k].iter().sum() gets the first window without a manual loop.