I am trying to have a bottom-up approach, so, the outermost loop will iterate over all lengths starting from 1 to n. The inner loop will iterate for the starting index of my window. I have my prefix sums computed, but once i have my starting index and ending index, how will i know at which point in my [L,R] I need to break in constant time, if i will loop, it will make it n cube!
The bottom up approach?
@ayushjain.iitg
It is actually a divide and conquer question
For each array there is only point about which you can break it
Range of elements is actually 1<=A[i]<=10^9
For each subarray TC is O(n) where n is size of subarray
So TC will be O(n^2)
Ya, I had realized that the question is not of DP, still I thought i might be wrong 
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.