描述
给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
样例
给出数组 [1, 3, -1, 2, -1, 2]
这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7
挑战
要求时间复杂度为 O(n)
dalao思路：left数组表示0-i这个区间内和最大的子数组，right数组表示i-nums.size()-1这个区间内和最大的子数组
public int maxTwoSubArrays(List<Integer> nums) {if(nums == null || nums.size() == 0) {return 0;}int maxSum = nums.get(0),curSum = 0;int []left = new int[nums.size()];int []right = new int[nums.size()];for (int i = 0;i < nums.size();i++) {curSum += nums.get(i);maxSum = Math.max(maxSum,curSum);curSum = Math.max(curSum,0);left[i] = maxSum;}curSum = 0;maxSum = nums.get(nums.size()-1);for (int i = nums.size()-1;i > 0;i--) {curSum += nums.get(i);maxSum = Math.max(maxSum,curSum);curSum = Math.max(curSum,0);right[i] = maxSum;}maxSum = Integer.MIN_VALUE;for (int i = 0;i < nums.size()-1;i++) {maxSum = Math.max(maxSum,left[i] + right[i+1]);}return maxSum;}//前后遍历、枚举法summary： 1、前后遍历的思想/interval 类型题也可以参考，因为两个子数组不能重合，先正向遍历得到0-i位置内最大子数组，maxSum = Math.max(maxSum,curSum);保证了left[i]会是这区间的最大值。也有一点动态规划dp的思路2、因为interval不能重合，所以正反遍历，并且有一个变量表示符合一个区间符合条件的值