连续子数组的最大和

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

思路一：根据数组规律

int FindGreatestSumOfSubArray( vector<int> array ) { int curSum = 0; int greatestSum = 0x80000000; //greatestSum为int所能表示的最小数 if ( array.empty() ) { return -1; } for ( int i = 0; i < array.size(); i++ ) { if ( curSum <= 0 ) { curSum = array[i]; } else { curSum += array[i]; } if ( curSum > greatestSum ) greatestSum = curSum; } return greatestSum; }