1:  /*

2:  @@

3:      Author:    Justinzhang

4:      Email:    uestczhangchao@gmail.com

5:      time:    2012-9-1 21:40:13

6:      desc:    find the max sum of sub arrys; This file was created at an earlier time;

7:              At that time, i didn't read the programming perls, in that book, there is a detailed

8:              discussion about this problem. The fastest algrithm can solve it in O(n) time;

9:              So if have spare time, read more of it.

10:  @@

11:  */

12:   

13:  #include 
     

14:  #include 
     

15:  #include 
     

16:  #include 
     

17:  using namespace std;

18:   

19:  template
     

20:  type getMax(type param1, type param2)

21:  {

22:      return (param1>param2 ? param1 : param2);

23:  }

24:   

25:  template
     
       type find_max_sum_of_subarray(vector
      
        vec)
      
     

26:  {

27:      type maxSum = 0;

28:      type curMaxSum = 0;

29:      for(unsigned int i=0; i < vec.size(); i++)

30:      {

31:          curMaxSum += vec[i];

32:          curMaxSum = getMax(0, curMaxSum);

33:          maxSum = getMax(maxSum, curMaxSum);

34:      }

35:      return maxSum;

36:  }

37:   

38:   

39:  int main()

40:  {

41:      int array[] = {-2, 5, 3,-6, 44, -8, 16};

42:      /* /!\ note that: to use array to initialize vector, the second parameter is the length of array,

43:         not the length of array minus 1.

44:      */

45:      vector
     
       vec(array,array+(sizeof array / sizeof(int)));
     

46:      cout << "find_max_sum_of_subArray: " << find_max_sum_of_subarray
     
      (vec) << endl;
     

47:      return 0;

48:  }