Xuất ra các dãy con ko giảm

[knownledge]

Anh em có ai làm giúp mình bài này đi, khó hiểu lắm "Nhập vào một mảng và: a.xuất ra các dãy con ko giảm. b.Tìm dãy con ko giảm có chiều dài lớn nhất. c.Tìm dãy con ko giảm có tổng lớn nhất."
các bạn co thể giải thích cho mình đoạn code chi tiết nhé. Cám ơn rất nhiều!

[kidkid]

Hix suy nghĩ chút nào , 1 dãy con không giảm thì là dãy con tăng , nhưng mà vẫn đề là dãy con này được tính từ hướng nào . Cứ default là từ đầu đến cuối trước nè .

Như vậy bây giờ chỉ là vấn đề tìm một dãy con tăng nữa thôi , thuật toán tìm dãy con tăng hình như là có rồi còn không thì cậu cứ nghĩ đơn giản như thế này :
Duyệt từ đầu đến cuối nếu mà giá trị thứ i+1 < i thì in dãy từ lúc duyệt đến i đấy . sao đó duyệt tiếp từ i+1 đến hết .

cứ mỗi lần tìm ra dãy đó thì lưu vào một mảng , với câu a thì xuất hết ra , với câu b thì strlen(A) tìm max rồi in ra, còn câu c thì tính tổng rồi coi thằng nào lớn nhất .

[virusvn]

virusvn có viết 1 bài giải thích về vấn đề này:
http://05dbb.13.forumer.com/viewtopic.php?t=277
Với đề là tìm các phần tử không giảm dài nhất (hoặc xóa ít nhất các số để tạo thành dãy không giảm dài nhất).
Tuy không đưa code C lên, nhưng giải thích khá dễ hiểu, bạn tự viết code nhé. Không phải là không muốn share, mà mấy bài này làm khi mượn máy người ta - lúc đó nghèo ko có USB, nên giờ ko còn code, thông củm.

[kidkid]

Uhm bài khá hay đấy ,đi sâu hơn câu hỏi của knowlege nhiều . Tuy nhiên nếu đi theo kiểu xóa ít nhất các số để tạo thành dãy ko giảm dài nhất thì sẽ hay hơn .

[hd_kinh_can]

Đây là bài toán cơ bản của phương pháp quy hoạch động thôi mà: Tìm dãy con không giảm dài nhất của N phần tử cho trước.
Các làm rất đơn giản

Gọi F[i] là độ dài dãy không giảm dài nhất từ phần từ a[1] đến a[i]
Khi đo, F[i] được tính bằng công thức:
F[i] = F[j] + 1 với j = 1..i-1; a[i] >= a[j] và F[j] là lớn nhất.
Có thể tìm được F[j] bằng 1 vòng lặp, nếu không tìm thấy thì F[i] = 1

Độ phức tạp thông thường là O(N^2), nếu cải tiến bằng cách chia nhị phân tìm kiếm j hoặc dùng cấu trúc Interval Tree thì độ phức tạp còn lại là O(N*log(2, N)). Sau khi tìm được F[i] với mọi i = 1..N rồi thì cứ dựa vào công thức trên mà truy vết thôi.
Bài toán này là bài toán đầu tiên mà sách thuật toán nào nói về quy hoạch động cũng nói đến.
Với những câu sau thì chỉ cần cải tiến rất nhỏ từ thuật toán trên là được.