Хамгийн их/бага нийлбэртэй дэд хэрчмийг хайх¶

Энд бид хамгийн их нийлбэртэй дэд хэрчмийг олох бодлого болон түүний зарим хувилбарыг (энэ бодлогыг онлайнаар бодох алгоритмыг оруулаад) авч үзнэ.

Бодлогын нөхцөл¶

$a[1 \ldots n]$ тоонуудын массив өгөгдсөн. Хамгийн их нийлбэртэй $a[l \ldots r]$ дэд хэрчмийг олох шаардлагатай:

$$ \max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].$$

Жишээ нь хэрэв $a[]$ массив дахь бүх бүхэл тоо сөрөг биш байсан бол хариу нь массив өөрөө байх байсан. Гэвч массив эерэг ба сөрөг тоо хоёуланг агуулж болох үед шийдэл нь тривиаль биш.

Хамгийн бага дэд хэрчмийг олох бодлого нь үндсэндээ ижил гэдэг нь тодорхой, та зүгээр л бүх тооны тэмдгийг өөрчлөх хэрэгтэй.

Алгоритм 1¶

Энд бид бараг илэрхий алгоритмыг авч үзнэ. (Дараа нь бид гаргахад арай хэцүү боловч хэрэгжүүлэлт нь бүр богино өөр алгоритмыг үзнэ.)

Алгоритмын тайлбар¶

Алгоритм маш энгийн.

Тав тухтай байлгах үүднээс бид дараах тэмдэглэгээ-г нэвтрүүлнэ: $s[i] = \sum_{j=1}^{i} a[j]$. Өөрөөр хэлбэл $s[i]$ массив нь $a[]$ массивын хэсэгчилсэн нийлбэрүүдийн массив юм. Мөн $s[0] = 0$ гэж тавина.

Одоо $r = 1 \ldots n$ индексээр давтаж, одоогийн $r$ утга бүрийн хувьд $[l, r]$ дэд хэрчим дээр хамгийн их нийлбэрт хүрэх оновчтой $l$-г хэрхэн хурдан олохыг сурцгаая.

Албан ёсоор энэ нь одоогийн $r$-ийн хувьд бид $s[r] - s[l-1]$-ийн утга хамгийн их байхаар $l$-г ($r$-ээс хэтрэхгүй) олох хэрэгтэй гэсэн үг. Тривиаль хувиргалтын дараа бид $s[]$ массивт $[0, r-1]$ хэрчим дээр минимум олох хэрэгтэй гэдгийг харж болно.

Эндээс бид шийдлийг шууд олж авна: бид $s[]$ массивт одоогийн минимум хаана байгааг зүгээр л хадгална. Энэ минимумыг ашиглан бид одоогийн оновчтой $l$ индексийг $O(1)$-д олж, одоогийн $r$ индексээс дараагийнх руу шилжихдээ энэ минимумыг зүгээр л шинэчилнэ.

Мэдээж энэ алгоритм $O(n)$-д ажилладаг бөгөөд асимптотоор оновчтой.

Implementation¶

To implement it, we don't even need to explicitly store an array of partial sums $s[]$ — we will only need the current element from it.

The implementation is given in 0-indexed arrays, not in 1-numbering as described above.

We first give a solution that finds a simple numerical answer without finding the indices of the desired segment:

int ans = a[0], sum = 0, min_sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum - min_sum);
    min_sum = min(min_sum, sum);
}

Now we give a full version of the solution, which additionally also finds the boundaries of the desired segment:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, min_sum = 0, min_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    int cur = sum - min_sum;
    if (cur > ans) {
        ans = cur;
        ans_l = min_pos + 1;
        ans_r = r;
    }
    if (sum < min_sum) {
        min_sum = sum;
        min_pos = r;
    }
}

Алгоритм 2¶

Энд бид өөр алгоритмыг авч үзнэ. Ойлгоход арай хэцүү боловч дээрхээс илүү дэгжин бөгөөд хэрэгжүүлэлт нь арай богино. Энэ алгоритмыг 1984 онд Жэй Кадане санал болгосон.

Алгоритмын тайлбар¶

Алгоритм өөрөө дараах байдалтай. Массиваар туулж, одоогийн хэсэгчилсэн нийлбэрийг ямар нэг $s$ хувьсагчид хуримтлуулъя. Хэрэв ямар нэг цэгт $s$ сөрөг байвал бид зүгээр л $s=0$ гэж ононо. Алгоритмын явцад $s$ хувьсагчид оногдсон бүх утгын хамгийн их нь бодлогын хариу байна гэж баталдаг.

Баталгаа:

$s$-ийн нийлбэр сөрөг болох эхний индексийг авч үзье. Энэ нь тэг хэсэгчилсэн нийлбэрээс эхэлж, эцэст нь сөрөг хэсэгчилсэн нийлбэр олж авна гэсэн үг — тиймээс массивын энэ бүх угтвар, түүнчлэн дурын дагавар сөрөг нийлбэртэй. Тиймээс энэ дэд хэрчим нь өөрийг нь угтвараар агуулах дурын дэд хэрчмийн хэсэгчилсэн нийлбэрт хэзээ ч хувь нэмэр оруулахгүй бөгөөд түүнийг зүгээр л хаяж болно.

Гэвч энэ нь алгоритмыг батлахад хангалтгүй. Алгоритмд бид үнэн хэрэгтээ зөвхөн $s<0$ тохиолдсон газруудын дараа шууд эхэлдэг ийм хэрчмүүдээр л хариу олоход хязгаарлагдана.

Гэхдээ үнэн хэрэгтээ дурын $[l, r]$ хэрчмийг авч үзье, $l$ нь ийм "критик" байрлалд байхгүй (өөрөөр хэлбэл $l > p+1$, энд $p$ нь $s<0$ байсан хамгийн сүүлийн ийм байрлал). Хамгийн сүүлийн критик байрлал нь $l-1$-ээс чанд эрт байгаа тул $a[p+1 \ldots l-1]$-ийн нийлбэр сөрөг биш болж таарна. Энэ нь $l$-г $p+1$ байрлал руу зөөснөөр бид хариуг нэмэгдүүлэх, эсвэл хамгийн муудаа өөрчлөхгүй гэсэн үг.

Аль нэг байдлаар, хариу хайхдаа зөвхөн $s<0$ гарсан байрлалуудын дараа шууд эхэлдэг хэрчмүүдээр өөрийгөө хязгаарлаж болно гэж таарна. Энэ нь алгоритм зөв болохыг баталж байна.

Implementation¶

As in algorithm 1, we first gave a simplified implementation that looks for only a numerical answer without finding the boundaries of the desired segment:

int ans = a[0], sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum);
    sum = max(sum, 0);
}

A complete solution, maintaining the indexes of the boundaries of the corresponding segment:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}

Холбогдох бодлогууд¶

Хязгаарлалттай хамгийн их/бага дэд хэрчмийг олох¶

Хэрэв бодлогын нөхцөл шаардлагатай $[l, r]$ хэрчимд нэмэлт хязгаарлалт тавьвал (жишээ нь хэрчмийн $r-l+1$ урт нь заасан хязгаарт байх ёстой), тайлбарласан алгоритмыг эдгээр тохиолдолд амархан ерөнхийлж болох магадлалтай — ямар ч байсан бодлого нь заасан нэмэлт хязгаарлалттайгаар $s[]$ массивт минимум олоход л оршино.

Бодлогын хоёр хэмжээст тохиолдол: хамгийн их/бага дэд матрицыг хайх¶

Энэ өгүүлэлд тайлбарласан бодлого нь том хэмжээст рүү байгалийн жамаар ерөнхийлөгдөнө. Жишээ нь хоёр хэмжээст тохиолдолд энэ нь өгөгдсөн матрицын дотор нь тоонуудын хамгийн их нийлбэртэй ийм $[l_1 \ldots r_1, l_2 \ldots r_2]$ дэд матрицыг хайх болж хувирна.

Нэг хэмжээст тохиолдлын шийдлийг ашиглан хоёр хэмжээст тохиолдлын хувьд $O(n^3)$-д шийдэл олоход амархан: бид $l_1$ ба $r_1$-ийн бүх боломжит утгаар давтаж, матрицын мөр бүрд $l_1$-ээс $r_1$ хүртэлх нийлбэрийг тооцоолно. Одоо бид энэ массивт $l_2$ ба $r_2$ индексүүдийг олох нэг хэмжээст бодлоготой болж, үүнийг аль хэдийн шугаман хугацаанд бодож болно.

Энэ бодлогыг бодох илүү хурдан алгоритмууд мэдэгдэж байгаа боловч тэдгээр нь $O(n^3)$-ээс тийм ч хурдан биш бөгөөд маш төвөгтэй (маш төвөгтэй тул тэдгээрийн олонх нь бүх боломжийн хязгаарлалтын хувьд далд тогтмолоороо тривиаль алгоритмаас доогуур байдаг). Одоогоор хамгийн сайн мэдэгдэж буй алгоритм $O\left(n^3 \frac{ \log^3 \log n }{ \log^2 n} \right)$ хугацаанд ажилладаг (T. Chan 2007 "More algorithms for all-pairs shortest paths in weighted graphs")

Чаны энэ алгоритм, түүнчлэн энэ салбар дахь бусад олон үр дүн нь үнэндээ хурдан матриц үржүүлэлт-ийг тайлбарладаг (энд матриц үржүүлэлт нь өөрчилсөн үржүүлэлтийг хэлнэ: нэмэхийн оронд минимум, үржүүлэхийн оронд нэмэхийг ашиглана). Хамгийн их нийлбэртэй дэд матрицыг олох бодлогыг бүх хос оройн хоорондох хамгийн богино замыг олох бодлогод шилжүүлж болох ба энэ бодлого нь эргээд ийм матриц үржүүлэлтэд шилжинэ.

Хамгийн их/бага дундажтай дэд хэрчмийг хайх¶

Энэ бодлого нь дундаж утга хамгийн их байх ийм $a[l, r]$ хэрчмийг олоход оршино:

$$ \max_{l \le r} \frac{ 1 }{ r-l+1 } \sum_{i=l}^{r} a[i].$$

Мэдээж хэрэв шаардлагатай $[l, r]$ хэрчимд өөр нөхцөл тавихгүй бол шийдэл нь үргэлж массивын хамгийн их элемент дээрх $1$ урттай хэрчим байх болно. Бодлого нь зөвхөн нэмэлт хязгаарлалт байвал л утга учиртай (жишээ нь хайж буй хэрчмийн урт доороос хязгаарлагдсан).

Энэ тохиолдолд бид дундаж утгын бодлоготой ажиллах үеийн стандарт арга-г хэрэглэнэ: бид хайж буй хамгийн их дундаж утгыг хоёртын хайлт-аар сонгоно.

Үүний тулд бид дараах дэд бодлогыг хэрхэн бодохыг сурах хэрэгтэй: $x$ тоо өгөгдсөн бөгөөд бид $a[]$ массивт (мэдээж бодлогын бүх нэмэлт хязгаарлалтыг хангасан) дундаж утга нь $x$-ээс их дэд хэрчим байгаа эсэхийг шалгах хэрэгтэй.

Энэ дэд бодлогыг бодохын тулд $a[]$ массивын элемент бүрээс $x$-г хас. Тэгвэл манай дэд бодлого үнэндээ дараах болж хувирна: энэ массивт эерэг нийлбэртэй дэд хэрчим байгаа эсэх. Бид энэ бодлогыг хэрхэн бодохыг аль хэдийн мэднэ.

Ингэснээр бид $O(T(n) \log W)$ асимптоттой шийдэл олж авлаа, энд $W$ нь шаардлагатай нарийвчлал, $T(n)$ нь $n$ урттай массивын дэд бодлогыг бодох хугацаа (тавьсан тодорхой нэмэлт хязгаарлалтаас хамааран өөр өөр байж болно).

Онлайн бодлогыг бодох¶

Бодлогын нөхцөл дараах байдалтай: $n$ тооны массив ба $L$ тоо өгөгдсөн. $(l,r)$ хэлбэрийн асуулгууд байх ба асуулга бүрт хариулахдаа $[l, r]$ хэрчмийн $L$-ээс багагүй урттай, хамгийн их боломжит арифметик дундажтай дэд хэрчмийг олох шаардлагатай.

Энэ бодлогыг бодох алгоритм нэлээд төвөгтэй. KADR (Ярослав Твердохлеб) өөрийн алгоритмаа Оросын форум дээр тайлбарласан.