Tìm dãy con tăng dần dài nhất trong chuỗi?

[Nhat_Pham1 (Minh Vương)]

Bài này đã suy nghĩ 2 - 3 ngày nhưng vẫn không tìm ra được thuật toán để giải quyết nó, viết in ra dãy tăng dần thì nó toàn thiếu 1 số, , mong mọi người cho em một chút giải thuật để em giải quyết nó. Chỉ cần giải thuật để em tự làm, không cần code.Thanks trước nha!!!

#include <iostream>
#include <cstring>
using namespace std;
main()
{
char s[] = "75367985789"; 
//VD o day no phai in ra la: 3679, 5789
int i , j , m;
m = s[0];
for(i = 0; i <= strlen(s); i++)
{
	if(m < s[i])
	{
	cout << s[i];
	m = s[i];
	}
	else
	m = s[i];
	cout << endl;
     }
}

[Gio (Gió)]

Tư tưởng: Thuật toán cần là quy hoạch động Với mỗi s[i] cần tìm dãy con tăng dài nhất kết thúc tại đó.
Giả sử đang dừng tại i để thõa mãn dãy con tăng dài nhất kết thúc tại i ta xét tất cả các phần tử đứng trước mà nhỏ hơn. rồi từ đó tìm dãy con dài nhất

Để sử dụng thuật toán cần 2 mảng max và trace dùng để lưu kết quả tốt nhất tại i và phần tử trước đó

MÌnh sẽ làm ví dụ với chuỗi "7536798"

i =0
max 1
trace [-1]  # không có phần tử nào trước đó

i=1
xét các phần tử đứng trước không có só nào < 5
max 1 | 1
trace -1 | -1

i=2
xét các phần tử đứng trước không có só nào < 3
max 1 | 1 | 1
trace -1 | -1 | -1

i=3
6 có 2 số nhỏ hơn là 5 và 3. ta chọn dãy dài nhất nếu nối 6 vào nên chọn 5 là số đầu
max 1 | 1| 1| 2
trace -1| -1 |-1 |1

i=4
7 có 3 số nhỏ hơn là 5 3 6, tuy nhiên chuỗi dài nhất nếu nối 7 vào là tại vị trí i=3 của 6
max 1 | 1 | 1 | 2 | 3
trace -1 | -1 | -1 | 1 | 3

i=5
9 có 3 số nhỏ hơn là 5 3 6 ,7 , tuy nhiên chuỗi dài nhất nếu nối 9 vào là tại vị trí i=4 của 7
max 1 | 1 | 1 | 2 | 3 | 4
trace -1 | -1 | -1 | 1 | 3 | 4 

i=6
8 có 3 số nhỏ hơn là 5 3 6 ,7 , tuy nhiên chuỗi dài nhất nếu nối 8 vào là tại vị trí i=4 của 7
max 1 | 1 | 1 | 2 | 3 | 4 | 4
trace -1 | -1 | -1 | 1 | 3 | 4 | 4 

Kết quả cuối cùng dãy tăng dài nhất là tìm G TLN của dãy max tại i =5
``
Bầy giờ ta tìm đó là chuỗi ntn? Đặt chuỗi kq là w=’’
w+=s[5] = “9”
tại i=5 trace[5]=4 : w+=s[4]= “97”
tai i=4 trace[4] =3: w+=s[3]=“976”
tai i=3 trace[3]=1 w+=s[1]=“9765”
tai i=1 trace[1]=-1 ket thuc
kết quả là đảo ngược chuỗi rev(w) = “5679”

[Nhat_Pham1 (Minh Vương)]

Ở i = 3 tại sao lại chon 5 vậy? và số đầu là sao vậy anh?

[Gio (Gió)]

Cái này là cách tìm gtln thôi. Nếu for từ đầu=> cuối thì chọn 5, còn ngược lại sẽ chọn 3. Có ý nghĩa cho cách chọn là nếu có nhiều dãy con tăng cùng độ dài. For 1 sẽ cho kq đầu tiên dài nhất. For thứ 2 sẽ cho kq cuối cùng

[Nhat_Pham1 (Minh Vương)]

Cứ mỗi lần có số lớn hơn thì thay đỗi Max, nhưng còn trace nó thay đổi ntn vậy a?

[Vo_Hao_Hao (Võ Hao Hao)]

Bạn có thể sửa lại thành :
> #include

#include <cstring>
using namespace std;
main()
{
char s[] = "75367985789"; 
//VD o day no phai in ra la: 3679, 5789
int i , j , m;
m = s[0];
for(i = 0; i <= strlen(s); i++)
{
	if(m < s[i])
	{
	cout << s[i];
	m = s[i];
	}
	if(m > s[i] && s[i] <s[i+1])
	{
	cout << s[i];
	m = s[i];
	}
	if(m > s[i])
	m = s[i];
	cout << endl;
     }
}

[noz1995 (Trần Hoàn)]

Cách dễ hiểu nhất là sử dụng std::list<string> rồi tách chuỗi ban đầu thành các chuỗi con cho vào trong list. Chuỗi nào dài bằng chuỗi dài nhất thì in ra