数组查询
Description
Given an array, the task is to complete the function which finds the maximum sum subarray, where you may remove at most one element to get the maximum sum.
给定一个数组，任务是完成查找最大和子数组的函数，在这个函数中，可以删除最多一个元素来获得最大和。
Input
第一行为测试用例个数T；后面每两行表示一个用例，第一行为用例中数组长度N，第二行为数组具体内容。
Output
每一行表示对应用例的结果。
Sample Input
1
5
1 2 3 -4 5
Sample Output
11
Solution
public class DeleteOneGetMaxSum {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int caseNum = in.nextInt();
for(int i = 0; i < caseNum; i++){
int len = in.nextInt();
int[] arr = new int[len];
for(int j = 0; j < len; j++){
arr[j] = in.nextInt();
}
System.out.println(deleteOneGetMaxSum(arr));
}
}
public static int deleteOneGetMaxSum(int[] arr){
int len = arr.length;
int[] left = new int[len];
int[] right = new int[len];
left[0] = arr[0];
int notDeleteMax = Integer.MIN_VALUE;
for(int i = 1; i < len; i++){
left[i] = Math.max(left[i - 1] + arr[i], arr[i]);
notDeleteMax = Math.max(notDeleteMax, left[i]);
}
right[len - 1] = arr[len - 1];
for(int i = len - 2; i >= 0; i--){
right[i] = Math.max(right[i + 1] + arr[i], arr[i]);
notDeleteMax = Math.max(notDeleteMax, right[i]);
}
int max = notDeleteMax;
for(int i = 1; i < len - 1; i++){
max = Math.max(left[i - 1] + right[i + 1], max);
}
return max;
}
}
