Танд бүхэл тоон дараалал өгөгдөхөд нийлбэр нь хамгийн их байх үргэлжилсэн дэд дарааллыг олно уу. Жишээ нь
-100 7 5 5 -6 3 -20 9 2 1
[2:6] дарааллын нийлбэр нь 14 тул манай хариу болно. Үргэлжлүүлж уншихаасаа өмнө өөрөө бодох гэж оролдоорой.
Боломжит бүх дэд дарааллыг шалгаж хариуг олвол хугацааны үнэлгээ O(N2) болно.
Бид энэ бодлогыг O(N) хугацаанд бодох боломжтой. Тоонуудыг зүүнээс баруун тийш нэг нэгээр нь уншиж авах бөгөөд тухайн тоог одоогын тооцоололдоо(одоогын дэд дараалалдаа) нэмэх үү эс нэмэх үү гэдгээ шийднэ. Нэмэхээр шийдсэн бол хариу болох max утгыг шинэчилнэ. Тухайн тоог авалгүй орхих ганц тохиолдол нь одоогын дарааллыг сөрөг болгох тохиолдол юм. Жишээ нь 5, 6, 1, -7, 8, -30, 1, 2, 3 гэсэн дараалал байлаа гэж бодоход [1:3] дэд дарааллын нийлбэр 12 болно. Одоогын max утга 12 болсон байна. Дараагын тоо болох -7 -г авбал, нийлбэр 5 болно. Нийлбэр сөрөг болоогүй учраас -7 -г авна. Дараа нь 8-г эргэлзэх зүйлгүй авснаар нийлбэр 13 болж, өмнө нь 12 байсан max 13 болж шинэчлэгдэнэ. Дараагын -30 -г авбал нийлбэр -17 болж, сөрөг болох тул энэ дарааллыг энэ хүргээд дуусгана. Учир нь энэ нийлбэр нь дараагын тоонуудад сөргөөр нөлөөлөх юм.
C++ бодолт.
