ในข้อนี้โจทย์ต้องการหาช่วงที่ติดกันที่มีผลรวมมากที่สุดที่ยาวไม่เกิน $w$

นิยามให้ $va[i]$ หมายถึงความคุ้มค่าของบ้านหลังที่ $i$ และนิยามให้ $pref(i)$ หมายถึง prefix sum หรือก็คือ $\sum \limits_{j=1}^{i} va[j]$ โดยเราสามารถคำนวณ $pref(i) = pref(i-1) + va[i]$ ได้สำหรับทุก ๆ $i$ ตั้งแต่ $i = 1,2,3,...n$ ดังนั้นผลรวมความคุ้มค่าของช่วง $[i,j]$ จึงเท่ากับ $pref(j) - pref(i-1)$

ดังนั้นการหาช่วงที่ติดกันที่มีผลรวมมากที่สุดสามารถเริ่มได้จากการกำหนดตัวแปร $mx$ แทนผลรวมของช่วงที่มากที่สุดและ $len$ แทนความยาวช่วงที่น้อยที่สุดที่ช่วงนั้นมีผลรวมเท่ากับ $mx$ โดยในตอนเริ่มต้นให้ $mx = 0$ และ $len = \infty$ ต่อมาไล่ในทุก ๆ $j$ ตั้งแต่ $j = 1,2,3,...,n$ หากพิจารณา ณ ตำแหน่ง $j$ ใด ๆ โดย $j$ เป็นตำแหน่งสิ้นสุดของช่วง เราต้องการหาตำแหน่ง $i$ ที่ทำให้ $pref(i) = \min \limits_{\max(1, j - w + 1) \leq k \leq j} \{ pref(k) \}$ กล่าวคือหาจุดเริ่มต้นช่วง $i$ ที่ทำให้ได้ความคุ้มค่าสูงสุดโดยความยาวช่วงไม่เกิน $m$ จากนั้นสามารถแยกพิจารณาออกเป็น 4 กรณีดังนี้

• กรณี 1: $i=j$ ไม่มีช่วงใดคุ้มค่าแก่การคุ้มครอง พิจารณา $j$ ถัดไป
• กรณี 2: $pref(j) - pref(i) > mx$ แปลว่า ช่วง $[i+1,j]$ เป็นคำตอบที่ดีกว่า เปลี่ยนให้ $mx = pref(j) - pref(i)$ และ $len = j - i$
• กรณี 3: $pref(j) - pref(i) = mx$ ค่าของ $mx$ ยังคงเดิมแต่เมื่อผลรวมเท่ากันความยาวสั้นที่สุดจะเป็นคำตอบ ดังนั้นเปลี่ยนให้ $len = \min ( len, j - i )$
• กรณี 4: $pref(j) - pref(i) < mx$ ไม่มีโอกาสที่จะเป็นคำตอบแน่นอน ให้พิจารณา $j$ ถัดไป

เมื่อพิจารณาสำหรับทุก ๆ $j$ ตั้งแต่ $j = 1,2,3,..n$ แล้ว $mx$ ยังคงเป็น $0$ แปลว่าไม่มีช่วงใดคุ้มค่าแก่การคุ้มครองเลย สามารถตอบด้วยคำตอบ $mx = 0$ และ $len = 0$ ได้เลย

สำหรับแต่ละ $j$ การไล่ทุก ๆ $i$ ตั้งแต่ $\max ( 1, j-w+1 )$ ถึง $j$ นั้นมี Time Complexity คือ $\mathcal{O}(N)$ โดยเมื่อคิดรวมทุก ๆ $j$ ตั้งแต่ $j = 1,2,3,...n$ จะมี Time Complexity รวม $\mathcal{O}(N^2)$ ซึ่งสามารถผ่านได้ใน Subtask 1 และ 2 เท่านั้น การจะ Optimize โปรแกรมให้เร็วขึ้นสามารถทำได้โดยใช้เทคนิค Minimum Sliding Window ด้วย Deque หรือ Double-ended Queue

การทำ Minimum Sliding Window ด้วย Deque นั้นจะเก็บเพียงข้อมูลที่ยังคงมีประโยชน์หรือสามารถนำไปใช้ได้ในอนาคตเท่านั้น กำหนด $q$ คือ Deque เก็บตัวแปรชนิด info ซึ่งเป็น struct ที่ประกอบด้วย idx คือ index ของ prefix sum ช่องต่าง ๆ ที่ยังเก็บไว้พิจารณา และ va คือค่า $pref(idx)$ สำหรับทุก ๆ $j$ ตั้งแต่ $j=1,2,3,...,n$

struct info {
  long long va, idx;
};
deque<info> q;

โดยจะมีลำดับขั้นตอนดังนี้

1. ลบข้อมูลที่ไม่มีประโยชน์: ในขณะที่ $|q| > 0$ และ $pref(j) \leq$ q.back().va แปลว่า q.back().va ไม่มีประโยชน์อีกต่อไปเพราะ index $j$ จะถูกเลือกแทน q.back().idx แน่นอนเพราะนอกจาก $pref(j) \leq$ q.back().va แล้ว $j \geq$ q.back().idx อีกด้วย ดังนั้นสามารถลบข้อมูลนี้ทิ้งได้เลยด้วยการใช้ q.pop_back()

2. ลบข้อมูลที่เกินขอบเขต: ในขณะที่ $|q| > 0$ และ q.front().idx $< j - w$ แปลว่าช่วง $[q.front().idx+1,j]$ มีความยาวเกิน $w$ จึงไม่สามารถนำมาพิจารณาได้อีกต่อไป ดังนั้นสามารถลบข้อมูลนี้ทิ้งได้เลยด้วยการใช้ q.pop_front()

3. เพิ่มข้อมูล: ข้อมูลในช่องที่ $j$ มีโอกาสที่จะเป็นคำตอบสำหรับ index ต่อ ๆ ไป ดังนั้นจึงต้องเก็บข้อมูลนี้ไว้พิจารณาต่อด้วย q.push_back({pref(j),j})

การทำตามลำดับดังกล่าวจะทำให้ $j -$ q.front().idx $+ 1 \leq w$ และ q.front().va เป็นค่าที่น้อยที่สุดใน $q$ แน่นอน จากเหตุผลดังกล่าวจะได้ว่า q.front().idx คือคำตอบของ $j$ สามารถนำมาคิดได้ตาม 4 กรณีด้านบนได้เลย

for (int j = 1; j <= n; j++) {
  while (!q.empty() && pref[j] <= q.back().va)
    q.pop_back();
  while (!q.empty() && q.front().idx < j - k)
    q.pop_front();
  q.push_back({pref[j], j});
  if (j == q.front().idx) {
    continue;
  } else if (mx < pref[j] - q.front().va) {
    mx = pref[j] - q.front().va;
    len = j - q.front().idx;
  } else if (mx == pref[j] - q.front().va) {
    len = min(len, j - q.front().idx);
  }
}

Time Complexity รวมของ Minimum Sliding Window นั้นจะเหลือเพียง $\mathcal{O}(N)$ เพราะทุก ๆ ข้อมูลจะเข้ามาอยู่ใน $q$ ด้วย q.push_back() เพียง 1 ครั้งและจะออกจาก $q$ ด้วย q.pop_back() หรือ q.pop_front() เพียง 1 ครั้งเช่นกัน เมื่อมีข้อมูลทั้งหมด $n$ ข้อมูลจึงมี Time Complexity รวม $\mathcal{O}(N)$