didn’t get the logic of cumulative sum. how we are using cumulative sum?
Generate Max Sum Method 2
Hello @harshit_03,
Cumulative Sum:
A cumulative sum is a sequence of partial sums of a given sequence.
Example:
A[]={1,2,3,-1,5,6} //Original array
Cum_Sum[]={0,1,3,6,5,10,16} //Cumulative Sum
//An extra element 0 is added as first element because Cum_Sum of index i depends upon Cum_Sum of index i-1.
Cum_Sum[i]=Cum_Sum[i-1]+A[i-1]
//Here we are storing the Cum_Sum for index i=0 of array A[] at i=1 of Cum_Sum[]
//i.e. cumulative sum for index i of A[] at i+1 of Cum_Sum[]
Start i from 1 to 6(n):
Cum_Sum[0]=0
Cum_Sum[1]=Cum_Sum[0]+A[0]=0+1=1
Cum_Sum[2]=Cum_Sum[1]+A[1]=1+2=3
…
…So on
What is the significance of the Cumulative Sum:
We can find the sum of all elements of a subset of an array.
How?
Sum of elements of subset starting from the index i to j
Subset_Sum=Cum_Sum[j+1]-Cum_sum[i]=10-1=9
example:
Sum of elements of subset starting from the index i=1 to j=4
Subset_Sum=Cum_Sum[5]-Cum_sum[1]=10-1=9
You might find the formulas different from what they have taken in the video.
Don’t worry about that.
Just understand the concept that will help you to understand the difference.
Hope, this would help.
Give a like, if you are satisfied.
1 Like