最大子数组问题：股票

题目简述：

购买一家股票，给若干股票不同时期预期价位，让你判断何时买何时抛可以获得最大收益。输入：各时期价位总数n以及每个价位。输出：最大收益以及买和投的时间（时期简单记为1-n）。

解题思路A：O(n)

考虑价位变化。由输入数据可以得到每次价位变化值a2-a1，并依次求和count，根据count是否为0把整个数组依次分为多个子数组，其中一个即为所求。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int n;
 9 
10 int main(){
11     int l,r,a1,a2,b2,maxn,count;
12     bool bo;
13     while(~scanf("%d",&n)){
14         maxn=count=0,bo=0;
15         scanf("%d",&a1);
16         for(int i=2;i<=n;i++){
17             scanf("%d",&a2);
18             b2=a2-a1;
19             a1=a2;
20             count+=b2;
21             if(count<0){
22                 count=0;
23                 bo=0;
24             }else{
25                 if(!bo){
26                     bo=1;
27                     l=r=i;
28                 }
29                 if(maxn<count){
30                     maxn=count;
31                     r=i;
32                 }
33             }
34         }
35         printf("%d: %d~%d
",maxn,l-1,r);
36     }
37     return 0;
38 }

View Code

解题思路B：分治

利用分治求解。考虑价位变化。由输入数据可以得到每次价位变化值a2-a1，问题即求最大子数组。递归分治，把数组分为均分两半，最大子数组有三种情况：左边，右边，或横跨中点。其中，横跨中点的情况，可以考虑把此数组分为两部分以mid为界，两边各求最大和相加，即为所求。然后求解。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 #define MAX 0x7fffffff
 9 #define N 100
10 
11 struct res{
12     int l,r,maxn;
13     bool operator < (const res &tmp)const { return maxn<tmp.maxn; }
14 };
15 
16 int n,a[N],b[N];
17 
18 res FindMaxn(int l,int r);
19 res FindMidMaxn(int l,int mid,int r);
20 
21 int main(){
22     while(~scanf("%d %d",&n,&a[1])){
23         for(int i=2;i<=n;i++){
24             scanf("%d",&a[i]);
25             b[i]=a[i]-a[i-1];
26         }
27         res tmp=FindMaxn(2,n);
28         printf("%d: %d~%d
",tmp.maxn,tmp.l-1,tmp.r);
29     }
30     return 0;
31 }
32 res FindMaxn(int l,int r){
33     res tmp;
34     if(l==r){
35         tmp.l=l;
36         tmp.r=r;
37         tmp.maxn=b[l];
38         return tmp;
39     }else{
40         int mid=(l+r)/2;
41         tmp=max(max(FindMaxn(l,mid),FindMaxn(mid+1,r)),FindMidMaxn(l,mid,r));
42         return tmp;
43     }
44 }
45 res FindMidMaxn(int l,int mid,int r){
46     int left=0,left_c=-MAX,right=0,right_c=-MAX,l_,r_;
47     for(int i=mid;i>=l;i--){
48         left+=b[i];
49         if(left>left_c) left_c=left,l_=i;
50     }
51     for(int i=mid+1;i<=r;i++){
52         right+=b[i];
53         if(right>right_c) right_c=right,r_=i;
54     }
55     res tmp;
56     tmp.l=l_,tmp.r=r_,tmp.maxn=left_c+right_c;
57     return tmp;
58 }

View Code