NEUOJ1302最大子序列

自己一开始的思路是找连续的正的一定是最大的其实不对，比如5 4 -1 2 8 0 9

如果照自己的找法的话，则最大的找的会是2+8，而实际应是5 4 -1 2 8最大，就这样。。。。。

所以正确的思路是：找一段最大连续子序列的和，则最大的就是1.这一段加上剩下的子序列中最大的子序列 2.最大子序列减去中间某最小子序列（证明略哪......）

所以问题基本转化为求某一段数的最大连续子序列。（附：求最小子序列可以区间全部数取反后求最大子序列....）

O（n）算法直接上代码吧。。这个自己体会下吧。有点类似于单调队列的思想。

很容易想通的。

for i:= 1 to n do

begin

s:=s+a[i];

if s<0 then s:=0;

if s>max then max:=s;

end;

当然这一切的前提都是建立在子序列的和要大于等于0的情况下的。

发现自己越来越爱ACM了

找BUG能力必须得在自己敲代码之后才OK

这道题自己的BUG出在找最大连续子序列的左端点上

感觉又学到了一个技巧！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #include<math.h>
 5 using namespace std;
 6 int a[1000005];
 7 
 8 int maxv(int x,int y)
 9 {
10     if(x>y) return 0;
11     int sum=0,max=-1001;
12     for(int i=x;i<=y;i++)
13     {
14       sum+=a[i];
15       if(sum<0) {sum=0;}
16       if(sum>max) {max=sum;}
17     }
18     return max;
19 }
20 
21 int minv(int x,int y)
22 {
23     if(x>y) return 0;
24     int sum=0,min=1002;
25     for(int i=x;i<=y;i++)
26     {
27         sum+=a[i];
28         if(sum>0) {sum=0;}
29         if(sum<min) {min=sum;}
30     }
31     return min;
32 }
33 int main()
34 {
35    //freopen("input.txt","r",stdin);
36     int num;
37     while(scanf("%d",&num)!=EOF)
38     {
39         memset(a,0,sizeof(a));
40         int max=-1002;
41         int sum=0;
42         int left=1,right,xx=1;
43         for(int i=1;i<=num;i++)
44         {
45             scanf("%d",&a[i]);
46             sum+=a[i];
47             if(sum<0) {sum=0;xx=i+1;}
48             if(sum>max) {max=sum;left=xx;right=i;}
49         }
50         int max_left=maxv(1,left-1);
51         int max_right=maxv(right+1,num);
52         int min_middle=minv(left,right);
53         int temp,ans;
54         if(max_left>=max_right) temp=max_left;
55         else temp=max_right;
56         if(temp+max>=max-min_middle) ans=temp+max;
57         else ans=max-min_middle;
58         //printf("%d %d %d %d %d %d\n",left,right,max,max_left,max_right,min_middle);
59         printf("%d\n",ans);
60     }
61     return 0;
62 }

View Code

for(int i=1;i<=num;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            if(sum<0) {sum=0;xx=i+1;}//亮点在xx上
            if(sum>max) {max=sum;left=xx;right=i;}//亮点在xx上~~~
        }