k урттай цонхыг array дээгүүр гулсуулж, дараалсан k тооны хамгийн их нийлбэрийг олдог арга.

Pre-IntermediateХугацаа: O(n)Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

a = [2, 1, 5, 1, 3], k = 2. Цонхнууд: 2 + 1 = 3, 1 + 5 = 6, 5 + 1 = 6, 1 + 3 = 4. Хамгийн их нь 6.

Цонх баруун тийш шилжихэд бүгдийг дахин нэмэхгүй: 3-аас 2-ыг хасаад 5-ыг нэмбэл 6 болно.

Энгийн аргаас санаа руу

Цонх бүрийн k тоог шинээр нэмбэл (n - k + 1) · k алхам. n = 100 000, k = 50 000 бол 2.5 тэрбум орчим.

Хажуу хоёр цонх k - 1 тоогоор давхцдаг. Цонх нэг алхам шилжихэд ганц тоо орж, ганц тоо гарна: s += a[i] - a[i - k]. Цонх бүрт ердөө хоёр үйлдэл.

Нэр томьёо ба тэмдэглэгээ

k
Цонхны урт. Цонх дараалсан k тоог хамарна.
s
Одоогийн цонхны нийлбэр.
best
Одоог хүртэлх хамгийн их нийлбэр.
a[i - k]
Цонхноос гарч буй тоо. Оронд нь a[i] орж ирнэ.
a
4
0
2
1
7
2
1
3
8
4
3
5
6
6
5
7
k = 3

Дараалсан 3 тооны нийлбэр хамгийн ихдээ хэд вэ? 3 тоо багтах цонхыг баруун тийш гулсуулж шалгая.

Алхам 1 / 16
Хурд
  • Цонх
  • Орж ирсэн тоо
  • Гарсан тоо
  • Хамгийн их нийлбэртэй цонх
Слайд 1 / 6

Sliding Window

Дараалсан 3 тооны нийлбэр хамгийн ихдээ хэд вэ? 3 тоо багтах цонхыг array дээгүүр баруун тийш гулсуулж шалгая.

sliding-window.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, a[100005];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
long long s = 0;
for (int i = 0; i < k; i++) s += a[i];
long long best = s;
for (int i = k; i < n; i++) {
s += a[i] - a[i - k];
if (s > best) {
best = s;
}
}
cout << best << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Дараалсан k тооны нийлбэрийг бүх байрлалд хурдан бодох. Цонх бүрийг дахин нэмэхгүй, ганц нэмэх, ганц хасах л хийнэ.

Яаж ажилладаг вэ?

1. Эхний k тоог нэмнэ: s = a[0] + … + a[k − 1]. Одоохондоо best = s. 2. Цонхыг нэг алхам баруун тийш гулсуулна: a[i] орж, a[i − k] гарна. s += a[i] − a[i − k]. 3. s > best бол best = s. 4. Array-н төгсгөл хүртэл давтана. Хариу нь best. Оролт: n k, дараа нь n тоо.

Яагаад зөв, хэр хурдан бэ?

i дахь алхмын дараа s нь a[i − k + 1]-ээс a[i] хүртэлх тоонуудын нийлбэр байна: өмнөх цонхны нийлбэрээс гарсан тоог хасч, орсон тоог нэмсэн. Цонх бүрийг яг нэг удаа best-тэй харьцуулдаг тул хариу зөв.

Эхний цонхонд k алхам, дараагийн цонх бүрт O(1): нийт O(n), нэмэлт санах ой O(1). n = 100 000 бол 100 000 орчим үйлдэл.

Түгээмэл алдаа

  • best-ийг 0-ээр эхлүүлэх. Бүх тоо сөрөг бол хариу 0 гэж буруу гарна. Эхний цонхны нийлбэрээр эхлүүл.
  • s-ийг int гэж зарлах. Нийлбэр k · 10⁹ хүрч хэтэрнэ, long long ашигла.
  • Гарч буй тоог a[i - k + 1] гэж андуурах. Шинэ цонх a[i - k + 1]-ээр эхэлдэг тул гарсан нь a[i - k].
  • k > n үед эхний loop array-гээс гадуур уншина. Оролтод 1 ≤ k ≤ n гэдгийг шалга.

Хязгаарын тохиолдол

  • k = n: ганц цонх, гулсуулах loop огт ажиллахгүй. Хариу бүх тооны нийлбэр.
  • k = 1: хариу нь хамгийн их тоо.
  • Бүх тоо ижил: бүх цонхны нийлбэр тэнцүү, best өөрчлөгдөхгүй.
  • Ижил нийлбэртэй цонх олон: s > best хатуу тэнцэтгэл биш тул хамгийн эхнийх нь үлдэнэ.

Өөрийгөө шалга

  1. Анхдагч жишээ 4 2 7 1 8 3 6 5, k = 3 дээр бүх цонхны нийлбэрийг бич.

    Хариу харах

    13, 10, 16, 12, 17, 14. Хамгийн их нь 17.

  2. n = 8, k = 3 бол хэдэн цонх байх вэ?

    Хариу харах

    6. Ерөнхийдөө n - k + 1.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = [5, 1, 3, 7, 2, 6], k = 2 үед s, best ямар утга авахыг алхам алхмаар бич.

    Hint харах

    Эхлээд s = 5 + 1 = 6.

    Хариу ба тайлбар

    s: 6, 4, 10, 9, 8. best: 6 → 10. Хариу 10.

  2. 2.Хамгийн их нийлбэртэй цонх аль index-ээс эхэлж байгааг хэвлэ.

    Hint харах

    best шинэчлэгдэх бүрт юу хадгалах вэ?

    Хариу ба тайлбар

    best = s; хийх бүрт pos = i - k + 1; хадгална. Эхлээд pos = 0.

  3. 3.Эерэг тоонуудын array өгөгдсөн. Нийлбэр нь S-ээс хэтрэхгүй хамгийн урт дараалсан хэсгийг ол.

    Hint харах

    Цонхны урт тогтмол биш. Баруун захыг нэмээд, нийлбэр хэтэрвэл зүүн захыг татна.

    Хариу ба тайлбар

    r бүрт s += a[r]. s > S байх хооронд s -= a[l]; l++;. Тэгээд цонхны урт r - l + 1 болно, хамгийн ихийг нь хадгална. l, r хоёулаа n удаа л хөдлөх тул O(n).

Жишээ

Оролт

8 3
4 2 7 1 8 3 6 5

Гаралт

17

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.