public class Main {
    public static void main(String[] args) {
        
        int[] A={13,-3,-25,20,-3,-16,-23,-3,20,-7,12,-5,-22,15,-4,7};
        Result r=maxSubArray(A, 0, A.length-1);
        
        
        /*
        Result r=FindMaxSubArray(A);
        */
        for(int i=0;i<A.length;i++){
            System.out.print(A[i]+"("+i+") ");
        }
        System.out.println();
        System.out.println(r.low);
        System.out.println(r.high);
        System.out.println(r.maxSum);
    }
    
    public static Result FindMaxSubArray(int[] A){
        int len=A.length;
        int maxSum=-65535;
        int low=0;
        int high=0;
        int sum=0;
        for(int i=0;i<len;i++){
            sum=0;
            for(int j=i;j<len;j++){
                sum+=A[j];
                if(sum>=maxSum){
                    maxSum=sum;
                    low=i;
                    high=j;
                }
            }
        }
        return new Result(low,high,maxSum);
    }
    
    
    public static Result maxSubArray(int[] A,int low,int high){
        if(low==high){
            return new Result(low,high,A[low]);
        }
        else{
            int mid=(low+high)/2;
            Result left_result=maxSubArray(A,low,mid);
            Result right_result=maxSubArray(A,mid+1,high);
            Result cross_result=maxCross(A,low,high);
            if(left_result.maxSum>right_result.maxSum&&left_result.maxSum>cross_result.maxSum)
                return left_result;
            else if(right_result.maxSum>left_result.maxSum&&right_result.maxSum>cross_result.maxSum)
                return right_result;
            else
                return cross_result;
        }
        
    }
    
    public static Result maxCross(int[] A,int low,int high){
        int mid=(low+high)/2;
        int left_low=mid;
        int left_high=mid;
        int left_max_sum=-65535;
        int right_low=mid+1;
        int right_high=mid+1;
        int right_max_sum=-65535;
        int sum=0;
        for(int i=mid;i>=0;i--){
            sum+=A[i];
            if(sum>=left_max_sum){
                left_max_sum=sum;
                left_low=i;
            }
        }
        sum=0;
        for(int i=mid+1;i<A.length;i++){
            sum+=A[i];
            if(sum>=right_max_sum){
                right_max_sum=sum;
                right_high=i;
            }
        }
        return new Result(left_low,right_high,left_max_sum+right_max_sum);
    }
    
    
    
    
}

class Result{
    public int low;
    public int high;
    public int maxSum;
    public Result(){
        low=0;
        high=0;
        maxSum=-65535;
    }
    public Result(int l,int h,int ms){
        low=l;
        high=h;
        maxSum=ms;
    }
}