Has someone faced this ? What could be possible reasons?
I have taken input array and segment tree array sufficiently large .
#include
#include <stdio.h>
#include
using namespace std;
struct node
{
long int maxPrefixSum;
long int maxSuffixSum;
long int totalSum;
long int maxSum;
};
int inputArr[54002];
node segmentTree[162006];
long int max(long int a , long int b)
{
if(a>b) return a;
return b;
}
void buildTree(int arrStart, int arrEnd, int segmentTreeIndex)
{
if(arrStart == arrEnd)
{
segmentTree[segmentTreeIndex].maxPrefixSum = inputArr[arrStart];
segmentTree[segmentTreeIndex].maxSuffixSum = inputArr[arrStart];
segmentTree[segmentTreeIndex].totalSum = inputArr[arrStart];
segmentTree[segmentTreeIndex].maxSum = inputArr[arrStart];
return;
}
int mid = arrStart + ((arrEnd - arrStart)/2);
buildTree(arrStart, mid, 2*segmentTreeIndex);
buildTree(mid+1, arrEnd, 2*segmentTreeIndex+1);
segmentTree[segmentTreeIndex].maxPrefixSum = max(segmentTree[2*segmentTreeIndex].maxPrefixSum,
segmentTree[2*segmentTreeIndex].totalSum + segmentTree[(2*segmentTreeIndex)+1].maxPrefixSum);
segmentTree[segmentTreeIndex].maxSuffixSum = max(segmentTree[(2segmentTreeIndex)+1].maxSuffixSum,
segmentTree[2segmentTreeIndex].maxSuffixSum + segmentTree[(2*segmentTreeIndex)+1].totalSum);
segmentTree[segmentTreeIndex].totalSum = segmentTree[2*segmentTreeIndex].totalSum + segmentTree[(2*segmentTreeIndex)+1].totalSum;
segmentTree[segmentTreeIndex].maxSum = max(segmentTree[2*segmentTreeIndex].maxSuffixSum + segmentTree[(2*segmentTreeIndex)+1].maxPrefixSum
, max(segmentTree[2*segmentTreeIndex].maxSum, segmentTree[(2*segmentTreeIndex)+1].maxSum));
}
long int getMaxSum(int queryStart, int queryEnd,
int segmentTreeNodeStart, int segmentTreeNodeEnd,
int segmentTreeIndex)
{
if ((queryEnd<segmentTreeNodeStart) || (queryStart>segmentTreeNodeEnd)){
return INT_MIN;
}
if((queryStart<=segmentTreeNodeStart) && (queryEnd>=segmentTreeNodeEnd)){
return segmentTree[segmentTreeIndex].maxSum;
}
int mid = segmentTreeNodeStart + ((segmentTreeNodeEnd - segmentTreeNodeStart)/2);
long int leftAns = getMaxSum(queryStart, queryEnd, segmentTreeNodeStart, mid, (2*segmentTreeIndex));
long int rightAns = getMaxSum(queryStart, queryEnd, mid+1, segmentTreeNodeEnd, (2*segmentTreeIndex)+1);
return max(leftAns, rightAns);
}
int main()
{
int N;
cin>>N;
for(int i = 1;i<=N;i++){
scanf("%d",inputArr[i]);
}
int M;
cin>>M;
buildTree(1, N, 1);
int qs, qe;
while(M)
{
cin>>qs>>qe;
printf("%ld\n",getMaxSum(qs, qe, 1, N, 1));
M–;
}
return 0;
}