Tổng con lớn nhất và ba trường hợp

Dãy con phải liên tục

Một tổng con S(i,j)=A[i]+…+A[j] lấy đủ các phần tử liên tiếp từ i tới j, gồm cả hai đầu. Với dãy không rỗng, yêu cầu tìm một dãy con **không rỗng** có tổng lớn nhất; không được tùy ý chỉ chọn các số dương nằm cách nhau. Chia tại mid. Dãy con tốt nhất hoặc nằm hoàn toàn bên trái, hoặc bên phải, hoặc có phần ở cả hai phía. Hai trường hợp đầu do đệ quy tìm. Đoạn chéo cần một hậu tố của nửa trái kết thúc tại mid và một tiền tố của nửa phải bắt đầu tại mid+1.

Tổng chéo qua ranh giới

Với A=[−4,5,−2,4,−6], mid=2: | Khả năng | Dãy con tốt nhất | Tổng | |---|---|---| | Nằm trái, chỉ số 0…2 | [5] | 5 | | Nằm phải, chỉ số 3…4 | [4] | 4 | | Qua ranh giới | [5,−2] ghép [4] | 3+4=7 | Đoạn tốt nhất là chỉ số 1…3, gồm [5,−2,4], tổng 7. Số −2 vẫn phải giữ vì nằm giữa5 và 4. Chọn riêng 5 và 4 để lấy 9 không còn là dãy con liên tục. Tìm hậu tố trái bằng cách cộng từ mid lùi về left và giữ tổng lớn nhất; tìm tiền tố phải từ mid+1 tiến tới right. Phải lấy ít nhất một phần tử mỗi phía cho đoạn chéo.

Toàn số âm vẫn phải chọn một đoạn không rỗng

Với A=[−7,−2,−5], tổng lớn nhất là −2, thuộc dãy con [−2]. Không trả 0 bằng cách chọn đoạn rỗng, vì yêu cầu với đầu vào không rỗng đang tìm đoạn không rỗng. Nếu đầu vào thực sự rỗng thì không có dãy con như vậy; hàm dùng tín hiệu riêng, không dùng0 như một tổng đã tìm thấy. Khi nhiều đoạn cùng tổng lớn nhất, chỉ cần một đoạn hợp lệ, chưa yêu cầu đoạn ngắn nhất hay đầu tiên.

Bài luyện

Với A=[−4,5,−2,4,−6], dãy con nào đạt tổng lớn nhất?

AChọn 5 và 4 bỏ−2, tổng 9.BToàn dãy có tổng −3.CDãy rỗng có tổng 0.D[5,−2,4] có tổng 7.

Bài luyện

Đoạn đi qua ranh giới được ghép thế nào?

AHậu tố trái kết thúc tại mid và tiền tố phải bắt đầu tại mid+1.BHai phần bất kì không cần liền nhau.CChỉ lấy một giá trị lớn nhất ở mỗi nửa.DLấy toàn bộ hai nửa trong mọi trường hợp.

Bài luyện

Tổng con không rỗng lớn nhất của [−7,−2,−5] là gì?

A2.B−2.C0.D−14.