How to solve this?

#1

what approach should i adopt for solving this?

#2

hello @pranjalarora98

try to build a recursive solution first.
solve(i,j) -> try to think how u can break this [i…j] into smaller subproblem

#3

yes that i am able to understand little little.
Initially l=0,u=arr.length-1
There should be some point suppose P where i divide.Now sum from l to p should be equal to p+1 till u.
Then some should be discarded?So shoud it be something
return 1+max(f(l,P-1),f(P+1,u))

#4

yeah correct.
but include p as well .

solve(i,j)-> 1 + max(solve(i,x) , solve(x+1,j) ) ; where x is index such that sum of [i…x] = sum of [x+1…j]

#5

ok so there should be some third argument also? which will store sum?How will sum be tracked then

#6

bro u have array u can calculate sum anytime right?

to optimise the sum calculation .
maintain a prefix sum array say pref.
sum of [i…x] = pref[x]-pref[i-1] // in O(1)