最大子序列和问题

正式开始学习数据结构和算法来,看到第一章,最大子序列和问题.

但是他这个算法当数据全为负时就有问题,当然,书上有前提.于是,稍加改变就通用了.

原文代码:

 1 int MaxSubSum1(const vector<int>& lhs)
 2 {
 3     int Length=lhs.size();
 4     int maxsum=0,currsum=0;
 5     for(unsigned i=0;i!=Length;i++){
 6         currsum+=lhs.at(i);
 7         if(currsum>maxsum)
 8             maxsum=currsum;
 9         else if(currsum<0){
10             currsum=0;
11         }
12     }
13     return maxsum;
14 
15 }

但是,这个不适合float和全负数情况,稍加改动,附上测试代码

View Code

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 template<typename T>     
 5 T MaxSubSum1(const vector<T>& lhs)
 6 {
 7     T Length=lhs.size();
 8     T maxsum=0,currsum=0;
 9     for(unsigned j=0;j!=Length;j++){
10         if(lhs.at(j)>maxsum)
11             maxsum=lhs.at(j);
12     }
13     for(unsigned i=0;i!=Length;i++){
14         currsum+=lhs.at(i);
15         if(currsum>maxsum)
16             maxsum=currsum;
17         else if(currsum<0){
18             currsum=0;
19         }
20     }
21     return maxsum;
22 
23 }
24 
25 void main()
26 {
27     vector<float> vec;
28     vec.push_back(20);
29     vec.push_back(20);
30     vec.push_back(30);
31     vec.push_back(40.7);
32     vec.push_back(60);
33     cout<<"向量=";
34     for(int i=0;i!=vec.size();i++)
35         cout<<vec.at(i)<<",";
36     cout<<endl<<"最大子序列和是"<<MaxSubSum1(vec)<<endl;
37 
38 }