Câu hỏi:

12/07/2024 787

Cho một dãy số bất kì A[0], A[1]..., A[n – 1]. Một tổng con được định nghĩa là tổng của một dãy con liên tục dạngSi, j = Ai + Ai + 1 + ... +Aj . Bài toán yêu cầu tìm và chỉ ra một tổng con và dãy con tương ứng có giá trị lớn nhất. Yêu cầu sử dụng kĩ thuật chia để trị.

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).

Tổng ôn toán Tổng ôn lý Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Em có thể áp dụng kỹ thuật chia để trị như sau:

1. Chia dãy số ban đầu thành hai dãy con bằng cách chia nó ở giữa.

2. Giải quyết hai dãy con bằng cách đệ quy áp dụng cùng thuật toán.

3. Tìm tổng con lớn nhất chứa phần tử ở giữa của dãy số ban đầu. Ta thực hiện điều này bằng cách tính tổng của phần tử đó cùng các phần tử liền trước và liền sau nó, rồi lưu lại tổng lớn nhất tìm được.

4. Tìm tổng con lớn nhất nằm hoàn toàn trong một trong hai dãy con đã giải quyết ở bước 5. Ta thực hiện điều này bằng cách đệ quy áp dụng lại thuật toán trên hai dãy con đó.

6. Tìm tổng con lớn nhất giữa phần tử ở giữa dãy con trái và phần tử ở giữa dãy con phải. Ta thực hiện điều này bằng cách tính tổng của phần tử giữa dãy con trái và phần tử giữa dãy con phải, rồi lưu lại tổng lớn nhất tìm được.

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Cho dãy số A, cần tìm phần tử mốt (mode) của A. Phần tử mốt là phần tử có số lần xuất hiện nhiều nhất trong A. Nếu tồn tại nhiều thì chỉ yêu cầu tìm ra một phần tử mốt. Yêu cầu sử dụng kĩ thuật chia để trị.

Xem đáp án » 11/05/2023 189

Câu 2:

Nâng cấp chương trình của nhiệm vụ 1 với yêu cầu bổ sung: Cần đưa ra kết quả là số lượng các cặp nghịch đảo và toàn bộ dãy các cặp chỉ số nghịch đảo đã tìm thấy. Ví dụ với A = [4, 5, 2, 10, 4] thì chương trình sẽ đưa ra giá trị 4 và dãy [(4, 2), (5, 2), (5, 4), (1, 4)].

Xem đáp án » 12/07/2024 152

Câu 3:

Khi làm việc với các danh sách mảng, nhiều trường hợp đòi hỏi cần kiềm ra các danh sách mảng đã được sắp thứ tự để áp dụng thuật toán phù hợp. Cho một dãy số, theo em làm thế nào để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần?

Xem đáp án » 12/07/2024 111

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP 1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 2 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 3 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP 4 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

Sách cho 2k7 ôn luyện THPT-vs-DGNL