Getting NZEC. Tried debugging a lot but could not find any flaw. Can someone point out where I might be going wrong.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class codeforces {
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
public static void main(String args[] ) throws Exception {
FastReader r = new FastReader();
int num = 1;
int n = r.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = r.nextInt();
}
SegmentTreeNode node = buildSegmentTree(arr,0,n-1);
int queries = r.nextInt();
while(queries-->0){
int st = r.nextInt()-1;int en = r.nextInt()-1;
SegmentTreeNode maxSubArray = getMaxSubArray(node,st,en);
System.out.println(maxSubArray.maxSubArraySum);
}
}
static class SegmentTreeNode{
int start;
int end;
int sum;
int maxPrefixSum;
int maxSuffixSum;
int maxSubArraySum;
SegmentTreeNode left;
SegmentTreeNode right;
SegmentTreeNode(int start,int end,int sum,int maxPrefixSum,int maxSuffixSum,int maxSubArraySum,SegmentTreeNode left,SegmentTreeNode right){
this.start = start;
this.end=end;
this.sum=sum;
this.maxPrefixSum=maxPrefixSum;
this.maxSuffixSum=maxSuffixSum;
this.maxSubArraySum=maxSubArraySum;
this.left=left;
this.right=right;
}
}
public static SegmentTreeNode buildSegmentTree(int arr[],int l,int r) {
if(l==r) {
return new SegmentTreeNode(l,l,arr[l],arr[l],arr[l],arr[l],null,null);
}
else {
int mid = (l+r)/2;
SegmentTreeNode left = buildSegmentTree(arr,l,mid);
SegmentTreeNode right = buildSegmentTree(arr,mid+1,r);
int sum = left.sum + right.sum;
int maxPrefixSum = Math.max(left.maxPrefixSum,left.sum+right.maxPrefixSum);
int maxSuffixSum = Math.max(right.maxSuffixSum,right.sum+left.maxSuffixSum);
int maxSubArraySum = Math.max(left.maxSuffixSum+right.maxPrefixSum,
Math.max(left.sum+right.sum, Math.max(left.maxSubArraySum, right.maxSubArraySum)));
return new SegmentTreeNode(l,r,sum,maxPrefixSum,maxSuffixSum,maxSubArraySum,left,right);
}
}
public static SegmentTreeNode getMaxSubArray(SegmentTreeNode node,int start,int end) {
if(node.start >= start && node.end<=end)return node;
else if(node.start>end || node.end<start)return null;
else {
int mid = (node.start+node.end)/2;
SegmentTreeNode left = getMaxSubArray(node.left,start,mid);
SegmentTreeNode right = getMaxSubArray(node.right,mid+1,end);
if(left==null)return getMaxSubArray(right,start,end);
if(right==null)return getMaxSubArray(left,start,end);
int sum = left.sum + right.sum;
int maxPrefixSum = Math.max(left.maxPrefixSum,left.sum+right.maxPrefixSum);
int maxSuffixSum = Math.max(right.maxSuffixSum,right.sum+left.maxSuffixSum);
int maxSubArraySum = Math.max(left.maxSuffixSum+right.maxPrefixSum,
Math.max(left.sum+right.sum, Math.max(left.maxSubArraySum, right.maxSubArraySum)));
return new SegmentTreeNode(start,end,sum,maxPrefixSum,maxSuffixSum,maxSubArraySum,null,null);
}
}
}