序列问题（续）

最大连续子序列

输出区间首元素，尾元素。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。时间复杂度O（n）,前缀和则为O(n^2)

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 #define Max 10000+10
 5 int main()
 6 {
 7     int n,s,e,sum,sumMax,S,E;
 8     int a[Max];
 9     int i,j;
10     freopen("in.txt","r",stdin);
11     while(scanf("%d",&n)==1&&n)
12     {
13         sum=0;
14         sumMax=-1;
15         for(i=0;i<n;i++)
16             scanf("%d",&a[i]);
17         s=a[0];
18         S=a[0];
19         for(i=0;i<n;i++)
20         {
21             sum+=a[i];
22             if(sum>sumMax)
23             {
24                 sumMax=sum;
25                 S=s;
26                 E=a[i];
27             }
28             else if(sum<0)
29             {
30                 sum=0;
31                 s=a[i+1];
32             }
33         }
34         if(sumMax<0)    {sumMax=0,S=a[0],E=a[n-1];}
35         printf("%d %d %d
",sumMax,S,E);
36     }
37 }

View Code

最长上升子序列 O(n^2)

dp方程：以a[i]结尾的LIS , dp[i]=max{dp[j]+1,dp[i]} (j<i)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 using namespace std;
 5 #define Max 100000+10
 6 int a[Max],dp[Max];
 7 int n;
 8 void solve()
 9 {
10     int res=0;
11     for(int i=0;i<n;i++)
12     {
13         dp[i]=1;
14         for(int j=0;j<i;j++)
15         {
16             if(a[j]<a[i])
17                 dp[i]=max(dp[i],dp[j]+1);
18         }
19         res=max(res,dp[i]);
20     }
21     printf("%d
",res);
22 }
23 int main()
24 {
25     int i,j;
26     while(cin>>n&&n)
27     {
28         for(i=0;i<n;i++)
29             cin>>a[i];
30         solve();
31     }
32 }

View Code

最长上升子序列 O(nlog(n))

这里的dp[i]表示长度为i的上升子序列的末尾元素，如果当前判断a[j],扫描一遍dp，找到一个最小的k,使得dp[k]>=a[j],此时dp[k-1]=a[j]

http://blog.csdn.net/dangwenliang/article/details/5728363

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 #define Max 10000
 6 #define INF 0x3f3f3f3f
 7 int a[Max],dp[Max];
 8 int n;
 9 void solve()
10 {    
11     fill(dp,dp+n,INF);
12     for(int i=0;i<n;i++)
13         *lower_bound(dp,dp+n,a[i])=a[i];
14     cout<<lower_bound(dp,dp+n,INF)-dp<<endl;
15 }
16 int main()
17 {
18     int i,j;
19     while(cin>>n&&n)
20     {
21         for(i=0;i<n;++i)
22             cin>>a[i];
23         solve();
24     }
25 }

View Code