连续最大子数组和

一，一个记录当前子数组和，一个记录最大子数组和

 1 class Solution {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 6         int cur = array[0];
 7         int maxv=array[0];
 8         for (int i=1; i<array.size(); ++i) {
 9             if(cur<0) cur=array[i];
10             else cur+=array[i];
11             maxv=maxv>cur?maxv:cur;
12         }
13         return maxv;
14     }
15 };

二，返回最大子数组的序列，如果有多个最大子数组，返回最长的那个。时间复杂度

 1 class Solution {
 2 public:
 3     /**
 4      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 5      *
 6      * 
 7      * @param array int整型vector 
 8      * @return int整型vector
 9      */
10     vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
11         // write code here
12         int cur=array[0];
13         int maxv=array[0]; 
14         int lv=0,rv=0;  // 保存结果
15         int lv2=0,rv2=0;  // 滑动区间
16         for(int i=1;i<array.size();++i){
17             if(cur<0){
18                 cur=array[i];
19                 lv2=i;
20                 rv2=i;
21             }
22             else {
23                 cur+=array[i];
24                 rv2+=1;
25             }
26             if((maxv==cur && rv2-lv2>rv-lv) || maxv<cur){
27                 maxv=cur;
28                 rv=rv2;
29                 lv=lv2;
30             }
31         }
32         vector<int> res;
33         for(int j=lv;j<=rv;++j){
34             res.push_back(array[j]);
35         }
36         return res;
37     }
38 };

心之所愿，永不相忘