Array operations

You are given an array $A$ consisting of $N$ elements. Your task is to find the maximal subarray sum after applying the following operation exactly once:

• Select any subarray and set all the elements in it to zero.

Example:

Input:  n=4 , a[]={-1, 4, -1, 2}
Output: 6

Approach

Java

public class ArrayOperations {
    public static void main(String[] args) {
        int n = 4;
        int[] a = { -1, 4, -1, 2 };
        int i;

        long[] pre = new long[n + 1];
        long[] suf = new long[n + 1];

        long max = 0l;
        long sum = 0l;
        for (i = 1; i <= n; ++i) {
            sum += a[i - 1];
            if (sum < 0)
                sum = 0l;
            max = Math.max(max, sum);
            pre[i] = max;
        }

        max = sum = 0l;
        for (i = n - 1; i >= 0; --i) {
            sum += a[i];
            if (sum < 0)
                sum = 0l;
            max = Math.max(max, sum);
            suf[i] = max;
        }

        long ans = 0l;
        for (i = 0; i <= n; ++i) {
            long cur = pre[i] + suf[i];
            ans = Math.max(ans, cur);
        }
        System.out.println(ans);
    }

}