Maximum Sub array using cumulative sum

#1

In the code for maximum sub array using cumulative sum, if all the elements of the array are positive then the output obtained is wrong. In the output:

Number of elements: 5
1 2 3 4 5
Sum is 14 for 2, 3, 4, 5,

But sum should be 15 including 1 in the sub array.

#2

Hey Amol, can you share the ide link of your code, which you have written for this problem.

#3

Hey thanks for the reply. But the code is providing wrong output in code blocks that I’m using but generates correct one on online compiler. Well I’m sharing the link, could you kindly acknowledge me with the problem.max_subarray.

#4

Hey Anmol, are you getting the error while compiling in code blocks? If so, then there are chances that may be you are using some old compiler.

1 Like
#5

Yes, I am only getting error in code blocks and on online compiler its working.

#6

Hi,
In your code
In the nested for loop
Line :
currentSum = cumSum[j] - cumSum[i-1];

Here, when i=0 and j=0
then cumSum[i-1]=cumSum[-1];Here -1 is invalid index.

So,
updated code:
if(i!=0)
currentSum = cumSum[j] - cumSum[i-1];
else
currentSum = cumSum[j];
Currently, you are using 2 loop so complexity O(n^2)
you can solve using one loop, see kadane algorithm O(n)
Hit like if u get it :slight_smile:

1 Like
#7

Thanks for the answer. I also suspected the invalid index part but wan’t sure that was the right guess or not.