查找子数组的最大和

题目：输入一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

 

例如： 输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

 

思路：本题基于一个简单的思想，加上一个正数会使原有的数变大，而加上一个负数会使原有的数变小，具体做法是依次遍历数组中的每一个数，并记下截至当前位置的最大和及当前和，如果当前和小于0就应该舍弃之，而从新的位置开始计算。另外对于一个既包含正数又包含负数的整型数组，其最大的子数组的和至少应该大于0。

 

代码：

//////////////////////////////////////////////
/// Find the greatest sum of all sub-arrays
/// input:
///      data: the data array
///      greatestsum: the greatest sum of all sub-arrays
/// output:
///      true: find success
///      false: find failed
/////////////////////////////////////////////
bool FindGreatestSumOfSubArray(vector& data, int& greatestsum)
{
 if(data.empty())
 {
  return false;
 }
 
 int begin = 0;
 int end = 0;
 int tempbegin = 0;
 int tempsum = 0;
 
 greatestsum = 0;
 
 for(int i = 1; i < data.size(); ++i)
 {
  tempsum += data[i];
  
  if(tempsum < 0)
   {
    tempsum = 0;
    tempbegin = i+1;
   }
  
   if(tempsum > greatestsum)
   {
    greatestsum = tempsum;
    begin = tempbegin;
    end = i;
   }
 }
 
 return true;
}