3.最长升序子序列 (动态规划)

题目解析：

AC代码：

#include
using namespace std;
#include
#include


int FindMaxSize(vector<int>& vec,int n){
    int result=1;//因为至少都有一个数
    vector<int> dp(n,1);//全部初始化为1
    for(int i=1;i<n;++i){
        for(int j=0;j<i;++j){
            if(vec[i]>vec[j]){
                dp[i]=max(dp[i],dp[j]+1);//取最大值
            }
        }
        //一层循环遍历完毕   更新result----最长子序列的长度
        result=max(dp[i],result);
    }
    return result;
}

int main()
{
    int n;
    while(cin>>n){//这里是多组输入
        vector<int>vec(n);
    for(int i=0;i<n;i++){
        cin>>vec[i];
    }
    cout<<FindMaxSize(vec,n)<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

题目变形：

题目分析：
上一题是有输入n，然后这一题没有输入n，直接叫你输入一个数组(实际上是输入字符串，然后提取数字进数组)，思想上和上一题是思路是一样的，但是要求出有多少个数字。

AC代码：

#include 
#include 
#include 
#include
#include
using namespace std;


int FindMaxStr(vector<int>& res, int n) {
    int result = 1;//用来保存最长长度
    vector<int>dp(n, 1);//创建一个二维数组  全部初始化为1
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (res[i] > res[j]) {
                dp[i] = max(dp[i], dp[j] + 1);//取最长值
            }
        }
        result = max(dp[i], result);//取最大值
    }
    return result;
}
int main()
{
   //这个题不是输入n ，而是输入一个字符串然后求出n
    string ans;
    getline(cin,ans);
    //创建一个数组
    vector<int>vec;
    int start=0;
    int i=0;
    while(i<ans.size()){
       if(ans[i]>='0' && ans[i]<='9'){
           start=i;
           int size=0;    
           while(ans[i]>='0' && ans[i]<='9'){
               i++;
               size++;
           }
           //截取字符串
           string s0=ans.substr(start,size);
           int num=0;
           stringstream  s1(s0);  //将数字字符串转成整型数字
           s1>>num; //输入流
           vec.push_back(num);
       }
       else 
           i++;
    }

    int n=vec.size();
    cout<<FindMaxStr(vec,n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

这里要额外扩展一下stringstream 流函数:

1.将int类型转成string类型

int main()
{
	stringstream result;
	string ans;
	int value=1000;
	//将int类型的数据放入到输入流中
	result << value;
	//从sstream中提取刚刚插入的int类型的数据，赋给string类型
	result >> ans;
	//输出
	cout<< ans<<endl;
	printf("%s\n",ans.c_str());
	
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.将string类型转成int类型

3.使用stringstream将多个字符串拼接 和将stringstream清空

int main()
{
   stringstream sstream;
   sstream << "first" <<" " <<"name";
   sstream << "second name" ;
   
   cout<<sstream.str()<<endl;
   //清空sstream
   sstream.str("");
   sstream << "third name";
   cout << sstream.str() <<endl;
 }
1
2
3
4
5
6
7
8
9
10
11
12

> 从上述代码执行结果能够知道：
1.可以使用 str() 方法，将 stringstream 类型转换为 string 类型；
2.可以将多个字符串放入 stringstream 中，实现字符串的拼接目的；
3.如果想清空 stringstream，必须使用 sstream.str(“”); 方式；clear() 方法适用于进行多次数据类型转换的场景。

> 清空 stringstream 有两种方法：clear() 方法以及 str("") 方法，这两种方法对应不同的使用场景。str("") 方法的使用场景，在上面的示例中已经介绍过了，这里介绍 clear() 方法的使用场景。
1

#include 
#include 
 
using namespace std;
 
int main()
{
    stringstream sstream;
    int first, second;
 
    // 插入字符串
    sstream << "456";
    // 转换为int类型
    sstream >> first;
    cout << first << endl;
 
    // 在进行多次类型转换前，必须先运行clear()
    sstream.clear();
 
    // 插入bool值
    sstream << true;
    // 转换为int类型
    sstream >> second;
    cout << second << endl;
 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

注意：在本示例涉及的场景下（多次数据类型转换），必须使用 clear() 方法清空 stringstream，不使用 clear() 方法或使用 str(“”) 方法，都不能得到数据类型转换的正确结果。下图分别是未使用 clear() 方法、使用 str(“”) 方法代替 clear() 方法时的运行结果不相同:

stringstream 用法参考：stringsteam用法
如有错误，多多指教!