//O(nlog(n))

public static int max_three(int a, int b, int c) {
    int temp=a>b?a:b;
    return temp > c ? temp : c;
}
public static int getCrossMax(int array[], int low, int mid, int hign) {
    int left_sum = 0;
    int right_sum = 0;
    int left_max = 0;
    int right_max = 0;
    for (int i = mid; i >= low; i--) {
        left_sum += array[i];
        if (left_sum > left_max) {
            left_max = left_sum;
        }
    }
    for (int i = mid + 1; i <= hign; i++) {
        right_sum += array[i];
        if (right_sum > right_max) {
            right_max = right_sum;
        }
    }
    return left_max + right_max;
}

public static int getMaxSubArraySum(int array[], int low, int hign) {
    if (low == hign) {
        return array[low];
    }

    int mid=low+(hign-low)/2;
    int left_sum = getMaxSubArraySum(array, low, mid);
    int right_sum = getMaxSubArraySum(array, mid + 1, hign);
    int cross_sum = getCrossMax(array, low, mid, hign);
    return max_three(left_sum, right_sum, cross_sum);
}

//O(n)
public static int process_online(int array[], int n) {
    int this_sum,max_sum;
    this_sum=max_sum=0;

    for (int i = 0; i < n; i++) {
        this_sum += array[i];
        if (this_sum > max_sum) {
            max_sum = this_sum;
        }
        if (this_sum <= 0) {
            this_sum = 0;
        }
    }
    return max_sum;
}