Query regarding cumulative sum

#1

when i=0 and j=0 then while calculating currentsum what will be its value when i=0 as cumSum (i-1) doesn’t exist when i=0?

#2

Hello, Initially we take the first element of the cumulative array equal to the first element of the given array. So it is like,
suppose we have 3 elements a1 a2 a3
and the cumulative sum of this is c1 c2 c3
then c1 = a1,c2 = c1 + a2, c3 = c2 + a3
I hope it is clear to you. In case it is clear to you pls mark it as resolve and provide the rating as well as feedback so that we can improve ourselves.
In case there is still some confusion pls let me know, I will surely try to help you out.
Thanks :slight_smile:
Happy Coding !!

#3

I queried about when both i and j =0 in the cumulative sum subarray algorithm as cumSum(i-1) will be invalid then.My query is not about how cumulative sum array is built but how it is manipulated to display the sum.

#4

Yes, that will be invalid at that time.

#5

Then how will it be evaluated like won’t garbage value disturb the result?

#6

Yes, you are right it can give error also as that index doesn’t exist as that will be -1. So in some compilers you surely will get an error. And truly speaking we need to take care of such cases as they can create problems. And yeah it won’t give any garbage value as the index doesn’t exist logically.

#7

hi @Senjuti256
we have to handle that case separately.
cumsum[0] = arr[0]
then start loop from i = 1.

I hope it is clear now.

#8

but sir has started the loop from 0 itself.

#9

but sir has started the loop from 0 itself.If we start from 1 then we might miss some subarrays including the 0th index

#10

@Senjuti256 that will work in some cases, but some compilers might give error, as my fellow TA has explained above. I told you how to handle the 0th case BEFORE the loop, please look at my previous reply properly.

#11

I too asked that if we start the loop from 1 then what will happen if the maximum sum subarray includes the element at the 0th index?

#12

@senjuti-2000 sorry i did not understand. Please elaborate.

#13

Suppose the 0th index element is a part of the subarray that yields the maximum sum.If now we start the loop from 1 then how can we include and check if the 0th index element should or should not be the part of the subarray yielding the maximum sum?

#14

@Senjuti256 I am sharing my code for this problem, I think you are confused, because there will be 2 separate loops, one for calculating the cumsum and one for calculating the maxsum and both will be handled differently.

#include<iostream>
using namespace std;
int maxSubarraySum(int array[1000], int numOfelements){
	int cumulativeSum[1000], i, j, tempSum, maxSum = -1, left = -1, right = -1;
	cumulativeSum[0] = array[0];
	for(i = 1; i < numOfelements; i++){
		cumulativeSum[i] = cumulativeSum[i - 1] + array[i];
	}

	for(i = 0; i < numOfelements; i++){
		for(j = i; j < numOfelements; j++){
			if(i > 0){
				tempSum = cumulativeSum[j] - cumulativeSum[i - 1];
			}
			else{
				tempSum = cumulativeSum[j];
			}
			//cout << tempSum << " ";
			if(tempSum > maxSum){
				maxSum = tempSum;
				left = i;
				right = j;
			}
		}
	}
	for(i = left; i <= right; i++){
		cout << array[i] << " ";
	}
	return maxSum;
}
int main(){
	int array[1000], numOfelements;
	cin >> numOfelements;
	for(int i = 0; i <numOfelements; i++){
		cin >> array[i];
	}
	cout << maxSubarraySum(array, numOfelements);
	return 0;
}