public Answer getMaxSubarrayDiff(int[] array) {
        int[] lmax = new int[array.length + 1];
        int[] lmin = new int[array.length + 1];
        int[] rmax = new int[array.length + 1];
        int[] rmin = new int[array.length + 1];
        lmax[array.length] = 0;
        lmin[0] = 0;

        int currentMaxSum = 0;
        int currentMinSum = 0;

        for (int i = 0; i < array.length; i++) {
            currentMaxSum += array[i];
            if (currentMaxSum > 0) {
                lmax[i + 1] = Math.max(currentMaxSum, lmax[i]);
            } else {
                currentMaxSum = 0;
                lmax[i + 1] = lmax[i];
            }
            currentMinSum += array[i];
            if (currentMinSum < 0) {
                lmin[i + 1] = Math.min(currentMinSum, lmin[i]);
            } else {
                currentMinSum = 0;
                lmin[i + 1] = lmin[i];
            }
        }
        currentMaxSum = 0;
        currentMinSum = 0;
        for (int i = array.length - 1; i >= 0; i--) {
            currentMaxSum += array[i];
            if (currentMaxSum > 0) {
                rmax[i] = Math.max(currentMaxSum, rmax[i + 1]);
            } else {
                currentMaxSum = 0;
                rmax[i] = rmax[i + 1];
            }
            currentMinSum += array[i];
            if (currentMinSum < 0) {
                rmin[i] = Math.min(currentMinSum, rmin[i + 1]);
            } else {
                currentMinSum = 0;
                rmin[i] = rmin[i + 1];
            }
        }
        Answer answer = new Answer();
        for (int i = 0; i <= array.length; i++) {
            if (Math.abs(lmin[i] - rmax[i]) > answer.diff) answer.diff = Math.abs(lmin[i] - rmax[i]);
            if (Math.abs(lmax[i] - rmin[i]) > answer.diff) answer.diff = Math.abs(lmax[i] - rmin[i]);
        }
        return answer;
    }