数组中两个子数组最大和

在一个数组中找两个子数组,求其最大和(子数组不重合,不空)

 

算法:

1. 设变量cur,max  cur=max=arr[0]
2. Cur<0 à cur=0  cur+=arr[i]    max=Math.max
3. 应用上面的,对arr从左遍历及从右遍历,得到L,R数组  L[i]/R[i]代表从左(右)开始到当前位置的子数组最大和
4. 求最大的L[i]+R[i+1]

public int getFromTwoArray(int[] arr){        int[] L = new int[arr.length];        int[] R = new int[arr.length];        int max;        L = this.getFromArray(arr);        R = this.getFromArray(arr, "right");        max = L[0] + R[1];        for(int i=1;i
     
      =0;i--){                if(cur<0){                    cur = 0;                }                cur += arr[i];                max = Math.max(cur, max);                maxArr[i] = max;            }            return maxArr;        }else{            throw new RuntimeException("error");        }    }