学步园

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

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

     
  思路：当我们遇到的是负数时，肯定会舍弃从后面算起，因为负数会使得和减少；同理，如果前面多个整数相加和为负数时也会舍弃。

      由此可得代码：

拓展问题1：
   
如果认为数组是环形的，即首尾相接(下标n-1的元素后面的元素下标为0)，求最大子段和。

        思路：最大值有两种情况。一、没有跨过a[n-1],a[0]等，即原问题，得到最大子串和max1,

                二、跨过a[n-1]，a[0]，此问题可以换成求最小子串问题，如：6,8,-3,2,-5,5,9,3,最大子串为：5,9,3,6,8，相当于该数组总数和减去最小字串(-3,2,-5)和，得到最大子串和max2

               取max1和max2的较大者

代码：