最长递增子序列

发表于   |   分类于   |  

1
注意这里是子序列，不是子串，所以不要求连续。

初始化

  • DP[i]=1 (所有i)
  • DP[i]=max{DP[i],DP[j]+1| j<i&&a[j]<a[i]}
    从前面的数组中找符合条件的，而不是根据最后一个

    只输出最长递增子序列的长度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int LIS(char* str)
    {
    	int len=strlen(str);
    	int *dp=new int[len];
    	for(int i=0;i<len;i++)
    	{
    		dp[i]=1; //最长递增子序列的最小值为1，即字符本身
    	}
    	int longest=1;
    	for(int i=1;i<len;i++)
    	{
    		for(int j=0;j<i;j++)
    		{
    			if(str[j]<=str[i])//这儿要根据题目，是否是严格递增
    			{
    				dp[i]=max(dp[i],dp[j]+1);
    			}
    		}
    		longest=max(dp[i],longest);
    	}
    	delete[] dp;
    	return longest;
    }

输出最长递增子序列

这里需要一个前缀数组，保存子序列中每个字符的前一个字符的位置。初始化为-1，表示初始时每个字符都是独立的。

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
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<stack>
#include<string.h>
#include<iostream>

using namespace std;
stack<char> s;
string LIS(char* str)
{
	int len=strlen(str);
	int *dp=new int[len];
	int *pre=new int[len];
	int longest=1;//保存LIS的长度
	int index=0;//保存LIS的最后一个字符的下标，通过它的pre一步步找到所有的字符。
	for(int i=0;i<len;i++)
	{
		dp[i]=1;
		pre[i]=-1;
	}
	for(int i=1;i<len;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(str[j]<str[i])
			{
				if(dp[i]<dp[j]+1)
				{
				    dp[i]=dp[j]+1;
					pre[i]=j;
				}
			}
		}
		if(longest<dp[i])
		{
			longest=dp[i];
			index=i;
		}
	}

	while(index>=0)
	{
		s.push(str[index]);
		index=pre[index];
    }
    string lstr="";
    while(s.empty()==false)
    {
    	lstr+=s.top();
    	s.pop();
	}
	return lstr;
}

int main()
{
    char str[100];
    while(scanf("%s",str)!=EOF)
    {
        string s=LIS(str);
        cout<< "长度： "<< s.length()<<endl;
        cout<<s<<endl;
    }
    return 0;
}