- 【描述】
-
求一個字符串的最長遞增子序列的長度
如：dabdbf最長遞增子序列就是abdf，長度為4
- 【輸入】
-
第一行一個整數(shù)0<n<20,表示有n個字符串要處理
隨后的n行，每行有一個字符串，該字符串的長度不會超過10000 - 【輸出】
- 輸出字符串的最長遞增子序列的長度
方法一：
=================================
=========
用一個數(shù)組保存以當(dāng)前字符作為結(jié)束的最長字串
對于一個字符串 s ，申請同樣長度的數(shù)組 X，X[i] 表示以s[i]結(jié)束的最長單調(diào)遞增子串
X[i] = max{ X[j]+1 } ,其中0≤j<i,且s[j]<s[i]
則s的最長升序子串為 max{ X[i] }
復(fù)雜度O(N^2)
#include<iostream>
#include<string>
using namespace std;
int main(){
int N;
cin >> N;
string s;
while(N--){
cin >> s;
int* x = new int[s.length()];
for (unsigned int i=0;i<s.length();i++)
x[i] = 1;
int max = 1;
for(unsigned int i=1;i<s.length();i++){
for(int j=i-1;j>=0;j--) {
if(s[j]<s[i]){
if(x[j]+1>x[i]){
x[i] = x[j]+1;
}
}
}
if(max<x[i]) max = x[i];
}
cout << max << endl;
}
return 0;
}
方法二：
?
==========================================
用一數(shù)組保存最長長度為下標(biāo)的最小字符。
#include<iostream>
#include <string>
using namespace std;
int main()
{
int n ;
cin>>n;
while(n--){
string str;
int count=1;
cin>>str;
int a[200];
a[0]=-999;
for (int i=0;i<str.length();i++){
for (int j=count-1;j>=0;j--){
if((int)str[i]>a[j]){
a[j+1]=str[i];
if(j+1==count) count++;
break;
}
}
}
cout<<count-1<<endl;
}
return 0;
}
?
方法三：
=======================================================
?如果字符的范圍有限,那么可以有O(N)時間的算法。
設(shè)串的字符集為S，包含N個元素，每個元素為Ak，Ai < Aj (0 <= i < j < N)。
設(shè)串T中以Ap結(jié)尾的單調(diào)遞增子序列長度為len(T, Ap)，則T的單調(diào)遞增子序列長度為Maxlen(T) = max(len(T,A0), len(T, A1), ..., len(T,An-1))。
如果給串T的末尾再添加一個字符Aq，則len(T + Aq, Aq) = len(T, Aq - 1) + 1。?
#include<stdio.h>
int length(char * s)
{
int len[128] = {0}, i, t;
for(; *s != '\0' ; s++){
t = len[*s - 1] + 1;
for(i = *s; i < 128 && len[i] < t; i++)
len[i] = t;
}
return len[127];
}
int main()
{
int n;
char s[10001];
for(scanf("%d\n", &n); n--;)
printf("%d\n", length(gets(s)));
return 0;
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
