Cumulative sum logic in maximum subarry

#1

i didnot get the logic of cumulative sum.
please elaborate this little bit for a clear understanding

#2

@abhinavakhil55 A cumulative sum is a sequence of partial sums of a given sequence. Let the cumulative sum array be:
2 6 11 17 25 This is the array which contains sum of all array elements upto 0th index at 0th pos, sum of all array elements upto 1st index at 1st position and so on…
Clearly if you want the sum of subarray starting from 1st index till the last index, you just need to subtract the cumulative sum at 0th position and you get the desired result.
Using this approach we get the formula “Sum of array = cs[j]-cs[i-1]”

Consider an array:
2 4 5 6 8
Now cumulative sum array:
2 2+4 2+4+5…
which is 2 6 11 17 25

Now to find the sum of any subarray:
say for subarray starting from 2nd index to 4th index:
Subarray sum is cumsum[4]-cumsum[2-1]=25-6=19 (according to formula)
Subarray sum from 2nd index to 4th index: 5+6+8=19 which is same as the formula.
It is simple, just apply your logic and check.

Hope this helps :slightly_smiling_face: