Vivek loves array game- Getting tle in one test case

#1

https://ide.codingblocks.com/s/188965

#2

Hey @Cheshtha
You need to store cumulative sum in an array called let’s say sum. Then if you need to get sum(i,j) simply do sum[j] - sum[i-1], j > i.

This is 0(n) while your current sum method is 0(n^2)
If your doubt is resolved please mark it as closed.

1 Like
#3


still tle

#4

@Cheshtha
I checked your approach again and saw it works in N^3.
You need an N^2 solution to work here.

This is a divide and conquer question. Lets say array is A and start and end indexes are s,e respectively.
Then take sum of elements from s to e.
Each array can have only one point of equality.
Find the point where prefix sum = total sum / 2.
if no such point return 0
each return 1+ max ( func(s, mid), func(mid+1,e) )

1 Like
#5

I got it now. Thanks