31.10. Bài toán tìm tổng con lớn nhất.Giả sử một công ty du lịch đã thiết kế một chương trình du...

Để giải bài toán này, ta có thể sử dụng phương pháp duyệt từng cặp điểm để tính tổng và so sánh với giá trị lớn nhất hiện tại. Dưới đây là một cách làm đơn giản:

1. Khởi tạo biến `imax`, `jmax` và `Smax` ban đầu bằng 0, 0, A[0] tương ứng.
2. Duyệt từng đoạn con bắt đầu từ i đến n với i từ 0 đến n-1.
3. Tính tổng của đoạn con từ i đến j và so sánh với `Smax`, nếu lớn hơn thì cập nhật `Smax`, `imax` và `jmax`.
4. In ra đoạn con tối ưu.

Sau khi thực hiện các bước trên, ta sẽ có chương trình du lịch con cho khách hàng với tổng lớn nhất.

Câu trả lời chi tiết và đầy đủ hơn có thể như sau:

```
A = [1, 7, -5, -9, 3, -1, 10, -6, 5]
n = len(A)
imax = 0
jmax = 0
Smax = A[0]

for i in range(n):
s = 0
for j in range(i, n):
s = s + A[j]
if s > Smax:
imax = i
jmax = j
Smax = s

print("Chương trình du lịch tối ưu là:")
print(imax, jmax)
for i in range(imax, jmax + 1):
print(A[i], end=" ")
```

Kết quả khi chạy chương trình sẽ in ra đoạn con với tổng lớn nhất và tối ưu cho chương trình du lịch của khách hàng.