Maximum Subarray Sum(Cumulative Sum)

#1

How did we derive the equation
currentSum=cumSum[j]-cumSum[i-1] ?
And what is the case when i=0?
cumSum[-1]??

#2

Hi, if your doubt is in reference to a particular code, please share it here. Also, it is not recommended to access the values at negative indices of arrays, so you should start the loop from i=1.

1 Like
#3

#include
using namespace std;

int main() {
int n;
cin >> n;
int arr[50], cumSum[50] = { 0 }, right = -1, left = -1, currentSum = 0, maxSum = 0;
//Input elements of array and do cummulative sum
cin >> arr[0];
cumSum[0] = arr[0];
for (int i = 1;i < n;i++) {
cin >> arr[i];
cumSum[i] = cumSum[i - 1] + arr[i];
}
//Maximum sum of subarray
for (int i = 0;i < n;i++) {
for (int j = i;j < n;j++) {
currentSum = 0;
currentSum = cumSum[j] - cumSum[i - 1];
if (currentSum > maxSum) {
maxSum = currentSum;
left = i;
right = j;
}
}
}
cout << "Maximum sum of subarray is : "<<maxSum<<endl;
cout << “Subarray is :”;
for (int k = left;k <= right;k++) {
cout << arr[k] << “,”;
}
return 0;

}

This is from lecture of maximum subarray sum

#4

In the statement currentSum = cumSum[j] - cumSum[i - 1]…we go through each and every subarray in the original array by subtracting the cumulative sum of current position(i) from a set position(j). by iterating i and j through the whole array, we compare the the cumulative sum from a max sum and then choose the maximum.
we start from 1 so as to avoid the negative index of array.

#5

the itrertion of i will start from 1 as in cumsum we are trying to find the value of subarray so when the first iteration first will run it will gave value of first subararray
or u can do like this
in j loop
if(i-1>=0){
currentsum=cursum[j]-cursum[i]
}
else{
currentsum=cursum[j]
}
.

#6

Hey Simby,
As you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.