最大子序列和

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <vector>
  4 using namespace std;
  5 int flag = 0;
  6 long maxsum(const vector<int>& a)//时间复杂度O（n3）
  7 {
  8     if (flag == 0)
  9     {
 10         return 0;
 11     }
 12     long maxsum = 0;
 13     for (int i = 0; i < a.size(); i++)
 14     {
 15         for (int j = i; j < a.size(); j++)
 16         {
 17             long thissum = 0;
 18             for (int k = i; k <= j; k++)
 19             {
 20                 thissum += a[k];
 21 
 22             }
 23             if (thissum>maxsum)
 24                 maxsum = thissum;
 25         }
 26     }
 27     return maxsum;
 28 }
 29 long maxsum2(const vector<int>& a)//时间复杂度O（n2）
 30 {
 31     if (flag == 0)
 32     {
 33         return 0;
 34     }
 35     long maxsum = 0;
 36     for (int i = 0; i < (int)a.size(); i++)
 37     {
 38         long thissum = 0;
 39         for (int j = i; j < (int)a.size(); j++)
 40         {
 41             thissum += a[j];
 42             if (thissum > maxsum)
 43                 maxsum = thissum;
 44         }
 45     }
 46     return maxsum;
 47 }
 48 long maxsum3(const vector<int>& a)//时间复杂度O（n）
 49 {
 50     if (flag == 0)
 51     {
 52         return 0;
 53     }
 54     long maxsum = 0, thissum = 0;
 55     for (int i = 0; i < (int)a.size(); i++)
 56     {
 57             thissum += a[i];
 58 
 59             if (thissum > maxsum)
 60                 maxsum = thissum;
 61             else if (thissum < 0)
 62             {
 63                 thissum = 0;
 64             }
 65         }
 66     return maxsum;
 67 }
 68 long maxsum4(const vector<int>& a,int left,int right) //时间复杂度n*log（n）
 69 {
 70     if (flag == 0)
 71     {
 72         return 0;
 73     }
 74     if (left == right)
 75     {
 76         if (a[left] > 0)
 77         {
 78             return a[left];
 79         }
 80         else
 81         {
 82             return 0;
 83         }
 84         
 85     }
 86     int center = (left + right) / 2;
 87     long maxleftsum = maxsum4(a, left, center);
 88     long maxrightsum = maxsum4(a, center + 1, right);
 89 
 90     long LBorder_maxsum = 0, LBorder_thissum = 0;
 91     for (int i = center; i >= left; i--)
 92     {
 93         LBorder_thissum += a[i];
 94         if (LBorder_thissum > LBorder_maxsum)
 95         {
 96             LBorder_maxsum = LBorder_thissum;
 97         }
 98     }
 99     long RBorder_maxsum = 0, RBorder_thissum = 0;
100     for (int j = center + 1; j <= right; j++)
101     {
102         RBorder_thissum += a[j];
103         if (RBorder_thissum > RBorder_maxsum)
104         {
105             RBorder_maxsum = RBorder_thissum;
106         }
107     }
108 
109     if (maxleftsum < maxrightsum)
110     {
111         maxleftsum = maxrightsum;
112     }
113     if (maxleftsum>(LBorder_maxsum + RBorder_maxsum))
114     {
115         return maxleftsum;
116     }
117     else
118     {
119         return (LBorder_maxsum + RBorder_maxsum);
120     }
121         
122 }
123 int main(void)
124 {
125     int K;
126     int temp;
127     
128     cin >> K;
129     vector<int>arry;
130     for (int i = 0; i < K; i++)
131     {
132         cin >> temp;
133         arry.push_back(temp);
134         if (temp >= 0)
135         {
136             flag = 1;
137         }
138 
139     }
140     //cout <<maxsum(arry)<< endl;
141     //cout <<maxsum2(arry)<< endl;
142     //cout <<maxsum3(arry)<< endl;
143     cout << maxsum4(arry,0,arry.size()-1) << endl; 
144     return 0;
145 }