hdu_1231（最大连续子序列）

http://acm.hdu.edu.cn/showproblem.php?pid=1231

最长公共子序列：

方法1：暴力枚举所有区间的连续和，维护最大和复杂度O(n^3）-->因为求区间和的时候重复了所以可以用S[i，j]=S[1,j]-S[1,i-1]来避免重复复杂度可以降到O(n^2)

方法2：分治复杂度O(nlongn)

　　　　分治法要求分而治之再合并；
　　　　分：分成三部分最大值，左，右，左and右；
　　　　治：左右可以递归求，左and右单独求；
　　　　合并：取三者最大值即可；
　　　　定义【i，j】表示起点终点都在区间里的最大和
　　　　将【i，j】上的最大和转换成max(【i,m】，【m+1，j】，起点在前一个区间，终点在后一个区间的最大和）这三者中的最大值；　　
　　　　其中前两个最大和可以递归实现，第三个定义的最大和一定是从中间向两遍扩大区间的过程中的最大值，可以分别遍历左右区间得到；

方法3：动态规划法复杂度O(n)

　　　　不知道有没有人看过算法导论的第四章的练习4.1-5，其中的题解给的dp思路需要维护两个数组，dp[j]表示扫描到j这个位置的时候的最大子区间和，adj[j]表示的是以j结尾的最大子区间和，更新很容易就能想出来，但是这个题要求保存的是编号最拷前的结果，所以可能要从后往前扫描处理

　　　　但是很简单的dp可以直接用dp[i]表示以i结尾的最大子区间和，最后再扫描一遍取最大值就是结果

　　　　求一个区间最大和，要求每个子区间都取到最大和；满足最优子结构；
　　　　子区间求最大和又是重叠子问题；
　　　　所以可以用动态规划求解；
　　　　首先如果我们要在O（n）的复杂度里算出来，那状态肯定是1维的即只枚区间的一个端点，那由对称性，起点和终点是同等的，所以方便起见我们要枚举的是区间的终点。
　　　　所以定义状态dp[i]是以i为区间的右端点的最大和;
　　　　先不管起点，如果我们知道了dp[i-1],dp[i]可以选择跟i-1连起来（连起来就是dp[i-1]+a[i],不连那就只有自己了a[i]），这样根据最大和我们知道“如果队友太坑，就卖了不要”否则就跟上队友；这里如果dp[i-1]<0就没必要连了
　　　　所以dp[i]=max(0,dp[i-1])+a[i];
　　　　然后我们要的答案就从各个终点的dp中选最大值就可以了；

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 const int N = 10020;
 7 int main()
 8 {
 9     int n;
10     int adjL[N];
11     int A[N];
12     int dp[N];
13     int max,maxid;
14     while(~scanf("%d",&n)){
15         if(n==0) return 0;
16         for(int i = 0; i < n ;i++){
17             scanf("%d",&A[i]);
18         }
19         max = A[0];
20         maxid = 0;
21         memset(dp,0,sizeof(dp));
22         memset(adjL,-1,sizeof(adjL));
23         dp[0] = A[0];
24         adjL[0] = 0;
25         for(int i = 1; i < n; i++){
26             if(dp[i-1]+A[i] >= A[i]){
27                 dp[i] = dp[i-1] + A[i];
28                 adjL[i] = adjL[i-1];
29             }
30             else{
31                 dp[i] = A[i];
32                 adjL[i] = i;
33             }
34             if(dp[i] > max){
35                 max = dp[i];
36                 maxid = i;
37             }
38         }
39         if(max<0) printf("0 %d %d
",A[0],A[n-1]);
40         else printf("%d %d %d
",dp[maxid],A[adjL[maxid]],A[maxid]);
41     }
42     return 0;
43 }

方法4：一遍扫描保存状态复杂度O(n)

　　设这一数组是a1,a2,.....,ai,ai+1,....an,首先初始化MAX=thisMAX=a1,start=end=1;然后对ai进行分析有MAX=（a[start],...,a[end]),thismax=(a[start],...,a[i-1]),其中i-1>=end;若thisMAX<0,则说明start......i-1中可以去掉end+1,...,i-1这一部分。对此我们可以用一个　　临时标界符temp来分开指示从i开始的连续和，这时thisMAX=0；开始新的求和，到此我们有两组“开始”，“结束”，”最大值“。第一组start，end，MAX；第二组：临时标界符temp，i-1，thismMAX；然后对i进行分析：

1.若ai<0,有假如thisMAX<0,则由于MAX至少大于等于0，所以不会更新；thisMAX>0(此时thisMAX一定是<=MAX的，不然在前面MAX的值一定会同步thisMAX的),又有thisMAX+ai<thisMAX<MAX，故仍旧不用更新

　　2.若ai>0,实际上就是上述的两组进行比较，若thisMAX>MAX,则进行更新start=temp，end=i;MAX=thisMAX；

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 int num[10008];
 6 
 7 int main()
 8 {
 9     int K,start,end,thisMax,MAX;
10     while(scanf("%d",&K)&&K)
11     {
12         int count=0,temp;
13         for(int i=0;i<K;i++) {scanf("%d",&num[i]);if(num[i]<0) count++;}
14 
15         if(count==K) {printf("0 %d %d
",num[0],num[K-1]);continue;}
16         start=end=0;
17         thisMax=MAX=num[0];
18 
19         for(int i=1;i<K;i++)
20         {
21           if(thisMax<0)
22           {
23               temp=i;
24               thisMax=0;
25           }
26           thisMax+=num[i];
27 
28           if(thisMax>MAX)
29           {
30               start=temp;
31               end=i;
32               MAX=thisMax;
33           }
34         }
35         printf("%d %d %d
",MAX,num[start],num[end]);
36     }
37     return 0;
38 }