Gss1

anyone...plz help me out !!

In your initialize finction you have assumed that the maximum subarray sum obtained from combination of two nodes is max(leftmax,rightmax).This is not true.The maximum subaray might stretch across both the intervals.You're nodes must have the following members.
1.MaxSum(M[] in your case)
2.MaxSuffixSum
3.MaxPrefixSum
4.Sum of all elements

you got it wrong....i am creating the tree for finding thee maximum value....not maximum sum !!

sry...i misread the problem...thanx for pointing it out

Hello Everyone,

I have been trying out this problem with very little success. I got rid of TLE but am unable to get rid of WA.

my logic :

I maintain two variables curr_sum and max_sum (both are initialized to 0). I start from the xth number and keep adding every number to curr_sum. Meanwhile i will be checking for two conditions.
1 . If curr_sum is greater than max_sum, then max_sum = curr_sum
2 . if curr_sum is < 0 then curr_sum = 0
In case if all the numbers are negative in the given range, then i will print the largest negative number in the sequence.

Here's my code.

#include<stdio.h>
#include<math.h>
long getNum()
{
    long i=0, temp = 0, neg=0, num[5], j;
    char c;
    c = getchar();
    while(c!='\n' && c!=' ')
    {
                  if(c=='-') neg = 1;
                  else
                  {
                      num[i] = c-48;
                      i++;
                  }
                  c = getchar();
    }
    i--;
    j = i;
    i = 0;
    while(j>=0)
    {
               float x = pow(10, j);
               temp += x*num[i];
               i++; 
               j--;
    }
    if(neg==1) temp = temp*(-1);
    return temp;
}
int main()
{
    long a[50000], count, m, temp = 0;
    count = getNum();
    while(count)
    {
                a[temp] = getNum();
                temp++;
                count--;
    }
    m = getNum();
    while(m)
    {
            long x, y, i;
            x = getNum();
            y = getNum();
            long curr_sum = 0, max_sum = 0, max_neg = -32000, neg_count = 0, count = 0;
            for(i=x-1;i<y;i++)
            {
                             if((curr_sum+a[i])>0)
                             {
                                                  curr_sum += a[i];
                                                  if(curr_sum>max_sum) max_sum = curr_sum;
                             }
                             else
                             {
                                 curr_sum = 0;
                             }
                             if(a[i]<0) 
                             {
                                        if(a[i]>max_neg) max_neg = a[i];
                                        neg_count++;
                             }
                             count++;
            }
            if(count==neg_count) printf("%d\n", max_neg);
            else printf("%d\n", max_sum);
            m--;
    }
    return 0;
}

I think your getNum() may be implemented incorrectly. Try redirect a input file to your program and you will know what I mean.
Your program can't pass the first test case (there are several of them in this problem). This may be caused by the incorrect getNum().
I replaced it by my own fast read function and got TLE at the 9th test case.
Regarding your algo, it is O(M * (y - x)). In the worst case, it is O(M * N). You will definitely get TLE. You need an algo O(M * log N) to get AC.
Read the posts about this topic. Hint: segment tree.

Thanks a lot for your reply

I implemented segment trees but still getting TLE. It would be very helpful if you could suggest where i am going wrong

#include<stdio.h>
#include<math.h>
long a[50000];
long max = 0, pre = 1, suf = 2, full = 3;
long maximum(a, b, c)
{
     if(a>=b)
     {
             if(a>=c) return a;
             else return c;
     }
     else
     {
         if(b>=c) return b;
         else return c;
     }
}
long* MaxSubArray(long x, long y)
{
     if(x==y)
     {
             long ret[4] = {a[x], a[x], a[x], a[x]};
             return ret;
     }
     else
     {
         long* left;
         long* right;
         long leftTemp[4], rightTemp[4];
         left = MaxSubArray(x, (x) + (y-x)/2);
         leftTemp[max] = left[max];
         leftTemp[pre] = left[pre];
         leftTemp[suf] = left[suf];
         leftTemp[full] = left[full];
         right = MaxSubArray((x) + ((y-x)/2) + 1, y);
         rightTemp[max] = right[max];
         rightTemp[pre] = right[pre];
         rightTemp[suf] = right[suf];
         rightTemp[full] = right[full];
         long ret[4];
         ret[pre] = maximum(leftTemp[pre], leftTemp[full]+rightTemp[pre], leftTemp[full]+rightTemp[full]);
         ret[suf] = maximum(rightTemp[suf], leftTemp[suf]+rightTemp[full], leftTemp[full]+rightTemp[full]);
         ret[full] = leftTemp[full]+rightTemp[full];
         ret[max] = maximum(leftTemp[max], rightTemp[max], leftTemp[suf]+rightTemp[pre]);
         return ret;
     }
}
long read()
{
     char c = getchar();
     int num[5], i = 0, j = 0, neg = 0;
     long temp = 0;
     while(c==' ' || c=='\n') c = getchar();
     while(c!=' ' && c!='\n')
     {
                if(c=='-') neg = 1;
                else 
                {
                     num[i] = c - 48;
                     i++;
                }
                c = getchar();
     }
     i--;
     j = i;
     while(j>=0)
     {
                float x = pow(10, j);
                temp += num[i-j]*x;
                j--;
     }
     if(neg==1) temp = temp*(-1);
     return temp;
}
int main()
{
    long count, m, temp = 0;
    count = read();
    while(count)
    {
                a[temp] = read();
                temp++;
                count--;
    }
    m = read();
    while(m)
    {
            long x, y;
            long *i;
            x = read();
            y = read();
            i = MaxSubArray(x-1, y-1);
            printf("%ld\n", i[0]);
            m--;
    }
    getch();
    return 0;
}

If you are new to segment tree, try to solve the easy one LITE first.

int mid = i + (j-1)/2

Still in shock 4r making mistake lyk dat ..

@leppy : thnks for the help..

but now it's showing wrong answer ...

Happy to help. Work with it a bit. Post your updated code if you can't figure it out.

managed to avoid WA but now got stuck on TLE ...

#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
#define ll long long
int sn,arr[MAX];
struct node{
    ll best,sum,lft,ryt;
	node(ll a = 0){
		best = sum = lft = ryt = a;
	}
	void merge(node a,node b){
		sum = a.sum+b.sum;
		lft = max(a.lft, a.sum+b.lft);
		ryt = max(b.ryt, a.ryt+b.sum);
		best = max(sum, max(lft,ryt) );
	}
}*segtree=NULL;
node query(int i,int j,int ri,int rj,int curr){
	if(rj<i || ri>j)
		return node();
	if(ri<=i&&rj>=j)
		return segtree[curr];
	int mid = i + (j-i)/2,l=2*curr+1;
    node a,b,temp;
	a = query(i,mid,ri,rj,l);
    b = query(mid+1,j,ri,rj,l+1);
    temp.merge(a,b);
    return temp;
}
void build(int i,int j,int curr){
	if(i>j)
		return;
	if(i==j){
		segtree[curr] = node(arr[i]);
		return;
	}
	int l = 2*curr+1,mid=i +(j-i)/2,r = 2*curr+2;
	build(i,mid,l);
	build(mid+1,j,r);
	segtree[curr].merge(segtree[l],segtree[r]);
}
void init(int n){
	sn = ceil(log2(n)+1);
	sn = 2*pow(2,sn);
	segtree = (node*)malloc(sn * sizeof(node));
	build(0,n-1,0);
}
int main() {
	int n,q,ri,rj;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	init(n);
	build(0,n-1,0);
	cin>>q;
	while(q--){
		cin>>ri>>rj;
		node temp = query(0,n-1,ri-1,rj-1,0);
        cout<<temp.best<<'\n';
	}
	free(segtree);
	return 0;
}

can you improve this code?? thnks for it!!

Cin/cout are slow.

used scanf & printf .. now it's giving wrong answer

If you're still having an issue, please post your updated code and edit the previous posts and remove the code.

here's the updated code:

#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
#define ll long long
int sn,arr[MAX];
struct node{
    ll best,sum,lft,ryt;
	node(ll a = 0){
		best = sum = lft = ryt = a;
	}
	void merge(node a,node b){
		sum = a.sum+b.sum;
		lft = max(a.lft, a.sum+b.lft);
		ryt = max(b.ryt, a.ryt+b.sum);
		best = max(a.ryt+b.lft, max(a.best,b.best));
	}
}*segtree=NULL;
node query(int i,int j,int ri,int rj,int curr){
	if(rj<i || ri>j)
		return node();
	if(ri<=i&&rj>=j)
		return segtree[curr];
	int mid = i + (j-i)/2,l=2*curr+1;
	if(j<=mid)
		return query(i,j,ri,rj,l);
	else if(i>mid)
		return query(i,j,ri,rj,l+1);
	else{
    	node a,b,temp;
		a = query(i,mid,ri,rj,l);
    	b = query(mid+1,j,ri,rj,l+1);
    	temp.merge(a,b);
	    return temp;
	}
}
void build(int i,int j,int curr){
	if(i>j)
		return;
	if(i==j){
		segtree[curr] = node(arr[i]);
		return;
	}
	int l = 2*curr+1,mid=i +(j-i)/2,r = 2*curr+2;
	build(i,mid,l);
	build(mid+1,j,r);
	segtree[curr].merge(segtree[l],segtree[r]);
}
void init(int n){
	sn = ceil(log2(n)+1);
	sn = 2*pow(2,sn);
	segtree = (node*)malloc(sn * sizeof(node));
	build(0,n-1,0);
}
int main() {
	int n,q,ri,rj;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	init(n);
	build(0,n-1,0);
	scanf("%d",&q);
	while(q--){
		scanf("%d %d",&ri,&rj);
		node temp = query(0,n-1,ri-1,rj-1,0);
        printf("%lld\n",temp.best);
	}
	free(segtree);
	return 0;
}

Why do you run build twice?

#include
using namespace std;
int main()
{
int n;
cin>>n;
int a[2n + 1];
for(int i=0;i<n;i++)
cin>>a[n+i];
for(int i=n-1;i>=1;i–)
a[i] = max(a[2i],a[2*i + 1]);
int q;
cin>>q;
for(;q>0;q–)
{
int l,r;
cin>>l>>r;
l–;
int res = a[n+l];
for(l+=n,r+=n ; l<r && l>=1 && r>1;l/=2,r/=2)
{
if(l%2 != 0)
{
res = max(res,a[l]);
l++;
}
if(r%2 != 0)
{
r–;
res = max(res,a[r]);
}
}
cout<<res<<"\n";
}
return 0;

}

Can anyone debug my code,. Got WA.