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

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

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

a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Дараалсан тоонуудын хамгийн их нийлбэр хэд вэ?

4 + (-1) + 2 + 1 = 6. Үүнээс их нийлбэртэй дараалсан хэсэг байхгүй. Хариу: 6.

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

Энгийн арга: эхлэл l, төгсгөл r бүрийг сонгоод нийлбэрийг бодно. Prefix sum ашигласан ч O(n²), n = 100 000 бол 5 тэрбум алхам.

Гол санаа: i дээр дуусах хамгийн сайн хэсэг бол i − 1 дээр дуусах хамгийн сайн хэсэг дээр a[i]-г нэмсэн, эсвэл a[i] ганцаараа. Өмнөх нийлбэр сөрөг бол түүнийг авах нь зөвхөн хохиролтой. Тиймээс cur < 0 бол cur = 0 болгоод a[i]-г нэмнэ. Бүх cur-ийн хамгийн их нь хариу.

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

cur
i дээр дуусах хамгийн их нийлбэртэй хэсгийн нийлбэр.
best
Одоог хүртэл олдсон хамгийн их нийлбэр. LLONG_MIN утгаас эхэлнэ.
subarray
Array-н дундаас тасралтгүй авсан хэсэг: a[l], a[l + 1], …, a[r].
DP
Том бодлогын хариуг жижиг бодлогынхоос гаргах. Энд шинэ cur нь өмнөх ганц cur-аас гарна.
a
-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8
cur
0
1
2
3
4
5
6
7
8
cur = 0best = −∞

Дараалсан тоонуудын нийлбэр хамгийн ихдээ хэд байх вэ? Сөрөг тоо байгаа тул бүгдийг нэмэх нь заавал зөв биш. Зүүнээс баруун тийш ганц удаа гүйгээд олъё.

Алхам 1 / 18
Хурд
  • a[i]
  • Одоогийн хэсэг
  • Шинэ cur
  • Хамгийн их нийлбэртэй хэсэг
Слайд 1 / 6

Хамгийн их нийлбэр

Дараалсан хэдэн тоо сонгоод нийлбэрийг нь хамгийн их болгоно. Хэсэг бүрийг шалгавал n × n орчим алхам болно. Kadane ганц удаа гүйгээд олно.

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

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

Сөрөг тоотой array-д хамгийн их нийлбэртэй дараалсан хэсгийг n алхамд олно. Ашиг, оноо, температурын өөрчлөлт гэх мэт олон бодлогод гардаг.

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

1. cur бол i дээр дуусах хэсгийн нийлбэр, best бол одоог хүртэлх хамгийн их нийлбэр. 2. cur сөрөг бол өмнөх хэсэг нийлбэрийг зөвхөн багасгана. Тиймээс cur = 0 болгож шинээр эхэлнэ. 3. cur += a[i]. 4. cur > best бол best = cur. Бүх тоо сөрөг байсан ч зөв ажиллана: тэдгээрийн хамгийн их нь (тэгт хамгийн ойр сөрөг тоо) хариу болно. Оролт: n, дараа нь n тоо.

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

i дээр дуусах хэсэг бүр a[i]-гаас гадна i − 1 дээр дуусах хэсгийг агуулдаг, эсвэл огт агуулдаггүй. Хамгийн их нь max(cur + a[i], a[i]). Код яг үүнийг хийдэг: cur сөрөг бол хаяна. Бүх i-г шалгадаг тул хариу best-д заавал орно.

Ганц loop: хугацаа O(n), санах ой O(1). n = 10⁶ бол сая алхам.

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

  • best-ийг 0-ээс эхлүүлэх. Бүх тоо сөрөг бол хариу 0 гарч буруу болно. LLONG_MIN эсвэл a[0]-ээс эхлүүл.
  • Нийлбэр int-ээс хэтрэх. a[i] ≤ 10⁹, n = 10⁵ бол 10¹⁴ хүрнэ. long long ашигла.
  • Хоосон хэсгийг зөвшөөрдөг эсэхийг анхаарах. Зөвшөөрдөг бол хариу хамгийн багадаа 0, үгүй бол сөрөг байж болно.

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

  • Бүх тоо сөрөг, жишээ нь [-3, -1, -2]: хариу −1, ганц тооноос тогтсон хэсэг.
  • Бүх тоо эерэг: хариу бүх array-н нийлбэр.
  • n = 1: хариу a[0].
  • Тэг ихтэй array: [0, 0, 0] бол хариу 0.

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

  1. a = [2, -1, 2] бол хариу хэд вэ?

    Хариу харах

    3. Бүх array: 2 − 1 + 2.

  2. a = [-5, -2, -8] бол хариу хэд вэ?

    Хариу харах

    −2.

  3. cur сөрөг болох нь юуг илэрхийлэх вэ?

    Хариу харах

    Өмнөх хэсгийг үргэлжлүүлэх нь ашиггүй. Шинэ хэсэг эхлүүлэх нь илүү.

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

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

  1. 1.a = [3, -4, 5, -1, 2, -6, 4] дээр i бүрт cur, best-ийг бич.

    Hint харах

    cur сөрөг болох бүрт дараагийн алхамд 0 болно.

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

    cur: 3, −1, 5, 4, 6, 0, 4. best: 3, 3, 5, 5, 6, 6, 6. Хариу 6: 5 + (-1) + 2.

  2. 2.Хариутай хамт хэсгийн эхлэл, төгсгөлийн index-ийг хэвлэ.

    Hint харах

    cur-ийг 0 болгох бүрт шинэ хэсэг i-гаас эхэлнэ.

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

    start хувьсагч нэмнэ. cur = 0 хийх үед start = i. best шинэчлэгдэх үед L = start, R = i гэж хадгална.

  3. 3.n × m хүснэгтийн хамгийн их нийлбэртэй тэгш өнцөгтийг ол. n, m ≤ 300.

    Hint харах

    Дээд, доод мөрийг сонгоод баганын нийлбэрүүд дээр Kadane ажиллуул.

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

    Мөрийн хос бүрт баганын нийлбэрийг prefix sum ашиглан O(m) хугацаанд гаргаад Kadane хийнэ. Нийт O(n² · m) ≈ 27 сая алхам.

Жишээ

Оролт

9
-2 1 -3 4 -1 2 1 -5 4

Гаралт

6

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

Бодлого

Хичээл

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