數(shù)組查詢(xún)

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.

給定一個(gè)數(shù)組，任務(wù)是完成查找最大和子數(shù)組的函數(shù)，在這個(gè)函數(shù)中，可以刪除最多一個(gè)元素來(lái)獲得最大和。

Input

第一行為測(cè)試用例個(gè)數(shù)T；后面每?jī)尚斜硎疽粋€(gè)用例，第一行為用例中數(shù)組長(zhǎng)度N，第二行為數(shù)組具體內(nèi)容。

Output

每一行表示對(duì)應(yīng)用例的結(jié)果。

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;
    }
}