这是一个在面试中出现概率非常高的一道题目，就拿我来说吧，面试了5家公司中。两家公司问了这道题目。可见，这道题目是非常经典的。

      解题思想也不是非常难。我熟悉的有；两种解题办法：

      1. 一直连加。终止当前序列的条件是连加的和是负数

      由于，一个数加上一个负数之后肯定是没有原来的数值大，所以。这肯定是没有意义的，终于。我们利用这个思想得到例如以下的解法。

      函数声明：

ll DutMaxSeqSubArray_1(int*, int);

typedef long long ll;

      源码：

/*非经常见的最大连续子数组的解法*/bool _DutMaxSeqSubArray = false;ll DutMaxSeqSubArray_1(int* A, int size){	if (!A || size <= 0)	{		_DutMaxSeqSubArray = true;		return -1;	}	ll result = 1 << 31;	ll currentSum = 0;	/*循环走一遍数组。遇到加和为负数时就開始下一轮加和*/	for (int i = 0; i < size; ++i)	{		if (currentSum <= 0)			currentSum = A[i];		else			currentSum += A[i];		if (result < currentSum)			result = currentSum;	}	return result;}

      2. 动态规划的思想：连续子数组最大和也一定是以某一个值结尾

      不管连续子数组有几个数，也不论和是多大。它总是以一个数结束的，而那个数肯定也是出如今数组中，所以，能够得到例如以下的递推公式： 

      以当前数结尾的最大连续子数组之和是：

      pData[i] = pData[i - 1] + A[i] || A[i]

      所以，能够得到例如以下的解法：

      函数声明：

ll DutMaxSeqSubArray_2(int*, int);

      源码：

/*动态规划的解法*/ll DutMaxSeqSubArray_2(int* A, int size){	if (!A || size <= 0)	{		_DutMaxSeqSubArray = true;		return -1;	}	ll result = 1 << 31;	ll currentSum = 0;	for (int i = 0; i < size; ++i)	{		/*		 *思想是，最大连续子数组肯定是以某一个数组元素结尾的。所以，		 *依照那个数字结尾时的最大加和就能够求得整个		 *数组的最大连续之和		 */		currentSum = DutMax
     
      (currentSum + A[i], A[i]);		result = DutMax
      
       (result, currentSum);	}	return result;}
      
     

      用到的模板函数：

template 
     
      T DutMax(T data1, T data2){	return data1 > data2 ? data1 : data2;}