递归---求子数组的最大和

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

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

因为时间复杂度为O(n), 以为着我们只能有for循环，不能有嵌套for循环；===》 我们只能从语义上去分析这个题目的破绽。

可以把一个规模为N的问题转化为规模为N-1的问题。所以这个从A[0]到A[n-1]的最大和子数组问题分解成：
1.       所求子数组中包含A[0]。如果不包含A[1]，则A[0]自己满足条件，此时Max（A[0]……A[n-1]）=A[0]。如果包含A[1]，则Max（A[0]……A[n-1]）=A[0]+Max（A[1]……A[n-1]）。
2.       所求子数组中不包含A[0]。Max（A[0]……A[n-1]）=Max（A[1]……A[n-1]）。
最终结果取以上三者的最大值即可，即Max（A[0]……A[n-1]）=max（ A[0], A[0]+Max（A[1]……A[n-1]）, Max（A[1]……A[n-1]））。

这样使得分类变多，但是元素变少了


所以这就好像踢皮球，最终把球踢给了A[n-2]和A[n-1]

如果只有这两个数： max(A[n-2],A[n-1])=max(A[n-2] , A[n-2]+A[n-1])
如果只有三个数：max(A[n-3],A[n-2],A[n-1]) = max(A[n-3],A[n-3]+max(A[n-2],A[n-1]),max(A[n-2],A[n-1]));
.....
Max（A[0]……A[n-1]）=max（ A[0], A[0]+Max（A[1]……A[n-1]）, Max（A[1]……A[n-1]））。


public void getMax(int[] arr){
   int max=0;
   int temp =0;
   for(int i=arr.length;i-2>=0;i--){
       if(i=arr.length-1){
          max = arr[i-2]>arr[i-2]+arr[i-1]?arr[i-2]:arr[i-2]+arr[i-1];
       }else {
          temp = arr[i-2]>arr[i-2]+max?arr[i-2]:arr[i-2]+max;
          max = temp>max?temp:max;
       }     
   }
}