子序列相关算法

1、最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是动态规划中的经典问题，顾名思义，即求两个序列最长的公共子序列（可以不连续）。

 1 #include <iostream>
 2 #include<string>
 3 using namespace std;
　　//使用动态规划算法；分为两种情况
 4 char a[102],b[102];
 5 int dp[102][102];
 6 int main()
 7 {
 8     string s1,s2;
 9     cin>>s1>>s2;
10     for(int i=0;i<s1.size();i++)
11     {
12         a[i+1]=s1[i];
13     }
14     for(int i=0;i<s2.size();i++)
15     {
16         b[i+1]=s2[i];
17     }
18 
19     for(int i=1;i<=s2.size();i++)
20     {
21         for(int j=1;j<=s1.size();j++)
22         {
23             if(b[i]==a[j])
24             {
25                 dp[i][j]=dp[i-1][j-1]+1;//最后一个字母相等
26             }
27             else
28             {
29                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
30             }
31         }
32     }
33     cout<<dp[s2.size()][s1.size()]<<endl;
34 
35     return 0;
36 }

2、最长连续子序列的和（分治法）

首先递归的进行对左右两边进行划分（直到只剩下一个元素，然后进行合并、比较）。有三种情况:1.最大值在左边；2.最大值在右边；3.最大值横跨左右两边；

 1 #include <iostream>
 2 using namespace std;
 3 int a[102];
 4 int maxsubsum(int left,int right)
 5 {
 6     int i,j;
 7     int maxleftsum,maxrightsum;
 8     int maxleftbordersum,leftbordersum;
 9     int maxrightbordersum,rightbordersum;
10     if(left==right)
11     {
12         if(a[left]>=0)
13         {
14             return a[left];
15         }
16         else
17         {
18             return 0;
19         }
20     }
21     int mid=(left+right)/2;
22     maxleftsum=maxsubsum(left,mid);
23     maxrightsum=maxsubsum(mid+1,right);
24     maxleftbordersum=0,leftbordersum=0;
25     for(int i=mid;i>=left;i--)
26     {
27         leftbordersum+=a[i];
28         if(leftbordersum>maxleftbordersum)
29         {
30             maxleftbordersum=leftbordersum;
31         }
32     }
33     maxrightbordersum=0,rightbordersum=0;
34     for(int i=mid+1;i<=right;i++)
35     {
36         rightbordersum+=a[i];
37         if(rightbordersum>maxrightbordersum)
38         {
39             maxrightbordersum=rightbordersum;
40         }
41     }
42     return max(max(maxleftsum,maxrightsum),maxleftbordersum+maxrightbordersum);
43 }
44 int main()
45 {
46     int res;
47     int n;
48     cin>>n;
49     for(int i=0;i<n;i++)
50     {
51         cin>>a[i];
52     }
53     res=maxsubsum(0,n-1);
54     cout<<res;
55     return 0;
56 }