wrong answer for spoj problem gss1

general
,
1

i dont know why this is giving wrong answer , it works perfectly fine on my machine bt still wrong answer …please suggest any test case or help me find the bug in the code . Here’s the link http://ideone.com/EO4Sw4
here’s the question link SPOJ.com - Problem GSS1

2

  1. This question asks you to find maximum sum subarray for given range xi and yi of array.

  2. example test case----
    5
    10 -1 10 -1 10
    1
    1 5
    your output is 30
    but correct is 28 because you have to take continuous array elements(that’s the meaning of subarray)
    you cant skip elements in subarray.(that was possible if question asked you for subset).

  3. spoiler ahead–
    this question is inteded for you to learn about segment trees.
    you can find the tutorial here(none of them is for this one. you will have to make some modifications in them).

    1. Segment Tree | Sum of given range - GeeksforGeeks
    2. Segment Tree | Range Minimum Query - GeeksforGeeks

    best of luck…

3

thanks for help , i understood my mistake …earlier i thought the same as you bt later i dont know why it was quite foolish out of me to understand this condition (Query(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y } ) as subset type problem , thinking v can skip indexes . Anyway thanks for help .

4

my pleasure…:slight_smile: