SKKN Sử dụng phương pháp quy hoạch động để giải một số bài toán có tính truy hồi trong ngôn ngữ lập trình c++

Phần I. ĐẶT VẤN ĐỀ:
1. Lý do chọn đề tài:
Chúng ta thấy Tin Học được ứng dụng vào hầu hết tất cả các lĩnh vực của cuộc sống và đã đóng vai trò rất lớn trong sự phát triển của xã hội.
Thấy được tầm quan trọng của Tin học, thế giới nói chung và Việt Nam nói riêng đã có những đầu tư lớn cho lĩnh vực này. Đặc biệt trong giáo dục nâng cao dân trí về Tin Học và đào tạo nguồn nhân lực có chất lượng cao.
Phụ huynh và các thế hệ học sinh sau này cũng đã bắt đầu chú trọng và đã chọn các nghành nghề liên quan đến công nghệ thông tin nhiều hơn.
Tuy nhiên  trong hệ thống giáo dục nước ta hiện nay môn Tin học chưa được quan tâm đúng với tầm quan trọng của nó. Tin Học đang bị xem là môn phụ trong trường học dẫn đến học sinh ít đầu tư cho môn học này, gây ra không ít khó khăn cho giáo viên trong nhà trường và đặc biệt chọn đội ngũ học sinh giỏi. Mặt khác môn Tin học có đặc thù riêng, học sinh giỏi đi thi chủ yếu chấm bài tự động trên phần mềm themis nên phụ thuộc lớn vào thời gian thực hiện (thời gian chạy) chương trình và giới hạn độ lớn dữ liệu mà bài toán yêu cầu. Vì vậy lập trình ngoài việc chú ý đến giới hạn dữ liệu bài toán thì cần lựa chọn thuật toán tối ưu để đảm bảo yêu cầu bài toán đặt ra. Vì vậy để giải bài toán trong Tin Học thường phải xác định được:
– Bài toán thuộc lớp nào.
– Sử dụng phương pháp tối ưu nào để giải nó.
Trong quá trình nghiên cứu và bồi dưỡng học sinh giỏi chúng tôi gặp khá nhiều bài toán về dãy con và bài toán xử lí xâu. Đây là một nội dung khá phổ biến trong các đề thi học sinh giỏi và là một nội dung khá khó. Với mong muốn tìm ra các giải pháp tối ưu cho các bài toán này, chúng tôi mạnh dạn trình bày sáng kiến kinh nghiệm: SỬ DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT SỐ  BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH
C++
2. Mục tiêu, nhiệm vụ của đề tài:
Nhằm giúp học sinh đứng trước 1 bài toán, xác định được là bài toán đó có thể áp dụng được quy hoạch động không và cách giải cụ thể như thế nào, đánh giá, so sánh được thời gian thực hiện chương trình (độ phức tạp của thuật toán). Cách nhận diện và lập công thức quy hoạch động
3. Đối tượng nghiên cứu:
Sử dụng phương pháp quy hoạch động để giải một số bài toán có tính truy hồi trong C++ như: Tìm dãy con; đếm dãy con; Tính tổng dãy con; và các bài toán liên quan đến xâu như tìm xâu con chung dài nhất và biến đổi xâu.
4. Phương pháp nghiên cứu:
Để trình bày sáng kiến kinh nghiệm này chúng tôi sử dụng kết hợp nhiều phương pháp như: Nghiên cứu tài liệu, nghiên cứu theo chuyên đề, thực nghiệm, so sánh, phân tích kết quả thực nghiệm, ý kiến đóng góp của đồng nghiệp trong thực tiễn giảng dạy
Phần II. NỘI DUNG NGHIÊN CỨU:
1. Cơ sở lý luận:
Sự phát triển như vũ bão của Tin học và những đóng góp lớn của Tin học trong sự phát triển xã hội không thể phủ nhận được, đặc biệt trong dịp dịch Covid 19 vai trò của Tin học đã được khẳng định, mọi người dân nói chung và phụ huynh học sinh nói riêng đã nhìn thấy được vai trò quan trọng của Tin học trong mọi lĩnh vực kinh tế, văn hóa và giáo dục. Chắc chắn mọi người đã có cái nhìn nhận khác và thấy môn Tin Học rất quan trọng.
Xã hội phát triển, đòi hỏi Tin học cũng phát triển để đáp ứng nhu cầu của xã hội. Để đáp ứng những đòi hỏi của sự phát triển đó phải có kế hoạch đào tạo bồi dưỡng những cá nhân có niềm say mê và có năng khiếu trong lĩnh vực tin học và trang bị vốn kiến thức cơ sở vững chắc, giúp cho mục tiêu đi trước đón đầu, rút ngắn khoảng cách về trình độ tin học giữa nước ta và thế giới.
Trong quá trình nghiên cứu, giảng dạy, chúng ta gặp rất nhiều các bài tập toán tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như: tham lam, quay lui, quy hoạch động, các giải thuật trên đồ thị… Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong quá trình ôn thi học sinh giỏi của trường, việc truyền đạt các kiến thức về một số thuật toán như: quay lui, quy hoạch động, tham lam, các giải thuật trên đồ thị… là rất cần thiết cho học sinh để phát triển tư duy và lập trình giải các bài toán tin học. Tạo lập và củng cố lòng say mê tìm hiểu và khám phá cho học sinh khi giải các bài toán tin.
Trong quá trình dạy bồi dưỡng chúng tôi nhận thấy, nếu học sinh thực hiện tốt việc lựa chọn và cài đặt chương trình tối ưu khi giải các bài tập về dãy con và các bài tập xử lí xâu nói riêng và các bài tập lập trình nói chung thì chất lượng học sinh giỏi sẽ được nâng cao.
2. Thực trạng vấn đề nghiên cứu:
Thực trạng dạy học môn Tin học trong trường phổ thông Phan Đăng Lưu hiện nay:
Hiện nay nhu cầu xã hội đang cần rất nhiều kĩ sư Công Nghệ Thông tin và lao động có trình độ cao. Tuy nhiên việc đào và bồi dương học sinh yêu thích môn tin học ở các trường  phổ thông gặp rất nhiều khó khăn.
– Môn Tin học vẫn đang bị xem là môn “phụ”, không tham gia thi tốt nghiệp hay đại học cao đẳng vì thế môn Tin Học chưa nhận được sự quan tâm của nhà trường cũng như phụ huynh và học sinh.
Mặt khác, để lập trình đòi hỏi học sinh phải có một kiến thức cơ bản tốt, phải có khả năng về tư duy và đam mê.
Vì vậy động viên và tuyển chọn được các em vào đội tuyển học sinh giỏi môn tin học ở trường rất khó
Trong thực trạng đó chúng tôi muốn tìm hiểu, nghiên cứu, và truyền những kinh nghiệm, hiểu biết của mình để truyền lại đam mê cho những học sinh ham thích môn Tin học.
3. Nội dung vấn đề nghiên cứu:
3.1. Tên chủ đề:
SỬ DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG ĐỂ GIẢI MỘT SỐ  BÀI TOÁN CÓ TÍNH TRUY HỒI TRONG NGÔN NGỮ LẬP TRÌNH C++
3.2. Cơ sở lý thuyết:
3.2.1. Khái niệm về phương pháp quy hoạch động:
Các thuật toán đệ quy có ưu điểm dễ cài đặt, tuy nhiên do bản chất của quá trình đệ quy, các chương trình này thường kéo theo những đòi hỏi lớn về không gian bộ nhớ và một khối lượng tính toán khổng lồ, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong những trường hợp như vậy, quy hoạch động là một trong những thuật toán được lựa chọn nhiều nhất.
Quy hoạch động (Dynamic programming) là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu trữ toàn bộ hay một phần kết quả tính toán tại mỗi bước với mục đích sử dụng lại. Bản chất của quy hoạch động là thay thế mô hình tính toán “từ trên xuống” (Top-down) bằng mô hình tính toán “từ dưới lên” (Bottom-up).
Từ “programming” ở đây không liên quan gì tới việc lập trình cho máy tính, đó là một thuật ngữ mà các nhà toán học hay dùng để chỉ ra các bước chung trong việc giải quyết một dạng bài toán hay một lớp các vấn đề. Không có một thuật toán tổng quát để giải tất cả các bài toán quy hoạch động.
Mục đích của phần này là cung cấp một cách tiếp cận mới trong việc giải quyết các bài toán tối ưu mang bản chất đệ quy, đồng thời đưa ra các ví dụ từ dễ đến khó để học sinh có thể làm quen và hình thành các kỹ năng trong việc tiếp cận các bài toán quy hoạch động.
3.2.2. Các bước giải bài toán quy hoạch động:
Có 4 bước để giải 1 bài toán bằng quy hoạch động:
Bước 1: Xây dựng hàm mục tiêu:
Áp dụng nguyên lý tối ưu của Bellman ta phân rã bài toán ban đầu thành các bài toán con cùng dạng có kích thước nhỏ hơn, sao cho việc giải quyết các bài toán con một cấp phụ thuộc vào kết quả của các bài toán con trước đó.
Bước 2: Xác định bài toán cơ sở:
Bài toán cơ sở là các bài toán con nhỏ nhất mà ta có thể biết ngay kết quả hoặc tính được kết quả dễ dàng. Đây chính là cơ sở để tính nghiệm cho các bài toán cấp lớn hơn.
Bước 3: Xây dựng công thức truy hồi:
Căn cứ vào ý nghĩa hàm mục tiêu, tìm mối liên hệ giữa các bài toán con các cấp, ta tiến hành xây dựng công thức tính kết quả của bài toán cấp i dựa vào kết quả của các bài toán con cấp trước nó. Lời giải được lưu vào mảng 1 chiều hoặc mảng 2 chiều (gọi là bảng phương án)
Bước 4:  Dựa vào bảng phương án, truy vết để tìm phương án tối ưu.
3.2.3. Biện pháp lựa chọn và cài đặt chương trình:
Khi nào thì dùng thuật toán quy hoạch động:
Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm hiểu, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải quyết những bài toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng là nội dung phương pháp quy hoạch động.
Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).
Nhận thấy:
 Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thoả mãn những yêu cầu dưới đây hay không:
 Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối
hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn.
 Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải (bộ nhớ, đĩa…) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được.
 Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước.
Cài đặt chương trình:
Các bước cài đặt một chương trình bằng phương pháp quy hoạch động
Bước 1. Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng phương án.
Bước 2. Dùng công thức truy hồi phối hợp những lời giải của những bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải.
Bước 3. Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.
Các hướng thực hiện quy hoạch động:
– Quy hoạch động ngược:
Phương pháp quy hoạch động ngược là phương pháp được sử dụng rộng rãi, vì nó khá tương ứng với suy nghĩ tự nhiên của chúng ta. Chúng ta đọc đề bài, suy nghĩ cách giải cho nó. Cách giải đó yêu cầu phải giải những bài toán nhỏ hơn, như kiểu làm toán ngày phải chứng minh các bổ đề vậy. Chúng ta tiếp tục suy nghĩ cho những bài toán con này, rồi tổng hợp để tìm ra lời giải cho bài toán lớn. Quá trình cứ tiếp tục như vậy, và quy hoạch động kiểu “ngược” này đang được xây dựng đúng như vậy.
Ngoài ra, về mặt lập trình, kiểu quy hoạch động này có mối quan hệ tương đối gần gũi với đệ quy. Một bài toán lớn được giải dựa vào các bài toán con tương tự nhau (và tương tự bài toán lớn) thì việc áp dụng đệ quy có thể là một phương pháp dễ dàng để code. Vì vậy, nhiều trường hợp, có thể coi quy hoạch động là một cách để tối ưu phương pháp đệ quy để giải một bài toán.
Ví dụ: Xâu con chung dài nhất
Cho hai xâu ký tự. Tìm độ dài xâu con chung nhỏ nhất giữa chúng. Ví dụ với 2 xâu “quetzalcoatl” và “tezcatlipoca” thì xâu con chung dài nhất sẽ là “ezaloa” với độ dài 6.
Với bài toán này, chúng ta sẽ lần lượt giải các bài toán con như sau:
Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu chung dài nhất giữa 2 xâu con được lấy ra đó. Dễ dàng thấy được rằng, lời giải của mỗi bài toán con sẽ phụ thuộc vào i và j, L(i, j). Và bài toán lớn sẽ được giải bằng cách lần lượt giải các bài toán con lần lượt từ L(0, 0) và tăng dần độ dài xâu được lấy ra cho đến khi chúng ta lấy ra toàn bộ xâu của đề bài.
Chúng ta hãy bắt đầu lần lượt các bài toán con. Đương nhiên, nếu một trong hai xâu là rỗng thì xâu con chung của chúng cũng rỗng. Vậy L(0, j) = L(i, 0) = 0. Nếu cả i và j đều dương, chúng ta cần suy xét một vài trường hợp.
1. Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không ảnh hưởng gì đến kết quả. Công thức ở đây sẽ là L(i, j) = L(i – 1, j).
2. Tương tự như trường hợp trên, ký tự cuối cùng của xâu thứ hai không ảnh hưởng đến kết quả thì L(i, j) = L(i, j – 1).
3. Trường hợp cuối cùng, nếu hai ký tự cuối cùng của hai xâu x1, x2 đều có mặt trong xâu con chung dài nhất. Dĩ nhiên là hai ký tự này phải là một thì điều này mới xảy ra, tức là x1 == x2. Trong trường hợp này, khi xoá đi bất cứ một ký tự nào trong hai ký tự đó đều khiến xâu con chung dài nhất ngắn đi 1 ký tự. Vậy rõ ràng là L(i, j) = L(i – 1, j – 1) + 1.
Trong cả ba trường hợp trên, chúng ta phải chọn ra trường hợp nào cho kết quả là xâu con chung dài nhất (với bài toán này thì chỉ cần đưa ra độ dài đó là đủ).
– Quy hoạch động xuôi:
Ngoài kiểu quy hoạch động ngược này, có một kiểu quy hoạch động “xuôi”. Tuy không phổ biến, kiểu quy hoạch động xuôi cũng khá khó áp dụng, nhưng quy hoạch động “xuôi” mang đến cho chúng ta nhiều tiện lợi. Kiểu xuôi này cũng cần duyệt qua các bài toán con từ nhỏ đến lớn, nhưng với mỗi bài toán con, chúng ta tính toán kết quả và từ đó tìm cách thực hiện một số phép tính để giải bài toán lớn hơn. Nghĩa là, với mỗi bài toán con, chúng ta sẽ nhìn về phía trước để xem phải giải bài toán tiếp theo như thế này từ bài toán hiện tại.
Phương pháp này khó áp dụng hơn phương pháp ngược kia, và cũng không phải bài toán nào cũng áp dụng được. Với mỗi bài toán, việc xác định bước tiếp theo tương đối khó khăn, thậm chí việc kiểm tra tính đúng sai của phương pháp cũng không hề dễ dàng.
Như chúng ta đã thấy ở những phần trước, thông thường, mỗi bài toán cần phải giải bằng cách tổng hợp kết quả từ một vài bài toán con trước đó. Vì vậy, cách quy hoạch động xuôi này chỉ sử dụng một bài toán con để tính toán trước bài toán tiếp theo sẽ chỉ cho ra một phần của kết quả chứ không phải kết quả cuối cùng. Vì vậy, để thực hiện quy hoạch động xuôi, việc điền sẵn một mảng các giá trị trung tính là điều bắt buộc (sau đó chúng ta sẽ cộng dồn kết quả vào mỗi khi giải được một bài toán con mới).
Ví dụ: Xâu con chung dài nhất: Với bài toán này, chúng ta có thể chọn giá trị trung tính là một số âm. Chúng ta sẽ tìm cách quy hoạch động xuôi như sau:
• L(0,0) = 0 là bài toán với hai xâu rỗng
• Với mỗi bài toán L(i, j) chúng ta sẽ tìm cách tính toán kết quả cho các bài toán lớn hơn. Lúc này, có 3 hướng phát triển tiếp:
1. Lấy thêm một ký tự từ xâu thứ nhất => Kết quả không thay đổi.
2. Lấy thêm một ký tự từ xâu thứ hai => Kết quả cũng không thay đổi.
3. Nếu ký tự tiếp theo của cả hai xâu giống nhau => Lấy tự từ này và độ dài xâu con chung tăng lên 1.
3.3. Các bài tập áp dụng:
3.3.1. Dạng bài toán về dãy con liên tiếp:
Mô hình:  Bài toán điển hình:
Cho dãy a1,a2,..an (1 <= n <= 106). có giá trị tuyệt đối không quá 104. Yêu cầu: Hãy lập trình tìm dãy con liên tiếp tăng dài nhất trong dãy a.
Dữ liệu vào: Đọc từ file DAYCON1.INP:
• Dòng đầu tiên nhập số N
• Dòng tiếp theo nhập các số A1, A2, …, AN
Dữ liệu ra: Ghi vào file DAYCON1.OUT một số nguyên dương duy nhất là độ dài của dãy con liên tiếp dài nhất tìm được.
Ví dụ
DAYCON1.INP  DAYCON1.OUT
10
1 3 4 2 4 5 6 1 2 3    4

Công thức:
Xây dựng hàm mục tiêu: L[i] là độ dài dãy con tăng liên tiếp dài nhất và kết thúc tại a[i].
Ta có công thức QHĐ để tính L(i) như sau:
+  Bài toán cơ sở: L[1] = 1
+  Xét a[i] (2≤i≤n):
• L[i]=1; (Với 1≤i≤ N và a[i] <a[i-1])
• L[i] = L[i-1] +1; (Với 1≤i≤ N và a[i] >a[i-1])
(độ dài đoạn con liên tiếp tăng sẽ nối thêm 1 đơn vị)
• Nếu a[i-1] >a[i] thì L[i] =1; (phần tử đầu cho dãy tăng mới)
Tính L[i] : Phần tử đang được xét là a[i] .Ta tìm đến phần tử a[i-1]< a[i]  có L[i1]. Khi đó nếu bổ sung a[i] vào sau dãy con a[1]…a[i-1] ta sẽ được dãy con tăng dần dài nhất xét từ a[1]…a[i].
Kết quả: độ dài lớn nhất của dãy liên tiếp = giá trị lớn nhất của mảng L.  Độ phức tạp của thuật toán này là o(n)
Cài đặt:
Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L[i]. Chương trình tính các giá trị của mảng L như sau:
#include <bits/stdc++.h> using namespace std; #define N int(1e6+1) int a[N],L[N],n; int main()
{     freopen(“DOANCON1.INP”,”r”,stdin);     freopen(“DOANCON1.OUT”,”w”,stdout);     cin >> n; int res=0;
for (int i = 1; i <= n; i++) cin >> a[i];       L[1]=1;     for (int i = 2; i <= n; i++)
{if (a[i-1] < a[i] ) L[i] = L[i-1]+1;     else L[i]=1;     res=max(res,L[i]);
}     cout << res;     return 0;
}
Bài toán cùng dạng:
Đề bài: Dãy con không giảm (Đề HSG tỉnh Bạc Liêu 2020-2021)
Cho số nguyên dương N và dãy số nguyên a1, a2, …, aN có giá trị tuyệt đối không quá 103. Dãy không giảm là dãy số có số hạng trước không lớn hơn số hạng sau.
Yêu cầu: Hãy lập trình tìm dãy con liên tiếp không giảm dài nhất trong dãy a.
Dữ liệu vào: Đọc từ file CAU1.INP:
• Dòng đầu tiên chứa số nguyên dương N(2≤N≤104)
• N dòng tiếp theo, mỗi dòng chứa một số nguyên là các phần tử của a.
Dữ liệu ra: Ghi vào file CAU1.OUT một số nguyên dương duy nhất là độ dài của dãy con liên tiếp dài nhất tìm được. Ví dụ:
CAU1.INP CAU1.OUT
7
-1
1
2
1
2
2
5 4
Bài này giải bằng phương pháp quy hoạch động: * Công thức:
+  Xây dựng hàm mục tiêu: L[i] là độ dài của đoạn con liên tiếp không giảm kết thúc tại a[i].
Độ dài đoạn con liên tiếp không giảm dài nhất là: max(L[])
+ Bài toán cơ sở: L[1] =1;
+  Xét a[i] (2≤i≤n):
– Nếu a[i-1] ≤ a[i] thì L[i] = L[i-1] +1 (độ dài đoạn con liên tiếp không giảm sẽ nối thêm 1 đơn vị)
– Nếu a[i-1] >a[i] thì L[i] =1; (phần tử đầu cho dãy không giảm mới) * Cài đặt chương trình:
#include <bits/stdc++.h>
#define N 10001 int a[N], f[N]; int n, res=0; using namespace std; int main()
{ freopen(“cau1.inp”, “r”, stdin); freopen(“cau1.out”, “w”, stdout);
cin>>n; for(int i=1; i<=n; i++)     cin>>a[i]; L[1]=1; for(int i=2; i<=n; i++)
{
if(a[i] >= a[i-1])         L[i] =L[i-1] +1;     else L[i]=1;     res= max(res, L[i]);
}      cout<<res;     return 0;
}
3.3.2. Dạng bài toán về dãy con không liên tiếp:
Mô hình: Bài toán điển hình:
Cho dãy a1,a2,..an (1 <= n <= 103).
Yêu cầu: Hãy lập trình tìm dãy con tăng dài nhất trong dãy a.
Dữ liệu vào: Đọc từ file DAYCON2.INP:
• Dòng đầu tiên nhập số N
• Dòng tiếp theo nhập các số A1, A2, …, AN
Dữ liệu ra: Ghi vào file DAYCON2.OUT
• Dòng 1: một số nguyên dương duy nhất là độ dài của dãy con dài nhất tìm được.
• Dòng 2: Đưa ra dãy con dài nhất tìm được Ví dụ
daycon2.inp daycon2.out
10
7  4  5  8  6  7  10  9  11  8    6
4  5  6  7  10    11

Cách 1:
Công thức:
 Phân rã bài toán:
Ta bổ sung 2 phần tử “lính canh” là a[0]= -∞ vào đầu dãy và a[n+1] = +∞ vào cuối dãy. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc tại a[n]+1.
→ Tổng quát: Cần tìm độ dài của dãy con tăng dài nhất từ a[i] →a[n+1]   Xây dựng hàm mục tiêu:
– Gọi L[i] là độ dài của dãy con tăng dài nhất bắt đầu tại a[i]  với (0≤i≤n+1)
– Suy ra kết quả của bài toán là: L[n+1] – 2
 Bài toán cơ sở: Ta dễ dàng thấy được L[n+1] =1;  (Dãy con bắt đầu từ a[n+1] = -∞, dãy con này gồm 1 phần tử là -∞ nên L[n+1]=1.
 Xây dựng công thức:
– Xét a[i]:
Nếu a[i] <a[j] (với 0≤i<j) thì L[i] = L[jmax] +1)
Dãy con đơn điệu tăng dài nhất bắt đầu từ a[i] sẽ được thành lập bằng cách lấy a[i] ghép vào đầu một trong những dãy con đơn điệu tăng dài nhất bắt đầu tại a[j]  mà a[i] < a[j] (i+1≤j≤n+1).
Vậy L[i] sẽ được tính: Xét tất cả các chỉ số j trong khoảng từ i+1 đến n+1 mà a[j] > a[i], chọn ra chỉ số jmax có L[jmax] lớn nhất.
 Truy vết:
Tại bước xây dựng L, mỗi khi tính L[i] =L[jmax]+1, ta đặt T[i]=jmax, để lưu lại dãy con tăng dài nhất bắt đầu tại a[i] sẽ có phần tử thứ hai kế tiếp là a[jmax].  Sau khi xây dựng xong 2 mảng L và T:
– Bắt đầu từ phần tử đầu tiên i=T[0].
– T[T[0]] là phần tử thứ 2 được chọn – T[T[T[0]]] là phần tử thứ 3 được chọn
……..
Tức là lúc đầu với i=T[0], ta chọn phần tử a[i], và các phần tử a[i] tiếp theo được chọn với i=T[i] (dựa vàng mảng vết T)