Max-subarray sum-run error

#1

https://ide.codingblocks.com/#/s/30564
code for https://hack.codingblocks.com/contests/c/512/1259
the logic has been covered in the video lectures, but it shows time limit exceeded upon submission to hackerblocks, if I remove long long int, then run-error.

https://ide.codingblocks.com/#/s/30572 -kadane’s algo
same case with kadane’s algo, again logic has been covered in videos

both the code work fine in my system ide, but i don’t use long long int for system ide

Please highlight the problem/issue and suggest changes.

thanks

#2

Kadane’s Code.

https://ide.codingblocks.com/#/s/30648

i have made two small changes. Now its working. I have commented the mistakes.

1 Like
#3

https://ide.codingblocks.com/#/s/30650

The O(N^2) approach, corrected the same mistake and its giving TLE. Runtime error was maybe due to making 10^7 size static long long array. It leads to memory limit exceed. The max size array you can make is around 5*10^6. If you want large arrays(not in this question), make them global. Global arrays can be as large as 10^8 MAX.

#4

One important observation was that question says maximum subarray sum and Ai>=0 always. So the best way is taking entire array in this case, and we dont even need KADANE for this.
NOTE, that your KADANE will fail for cases like,
INPUT:
5
-1 -2 -3 -4 -5
EXPECTED OUTPUT:
-1
YOUR OUTPUT:
0
So handle this case separately that if all the elements are negative, then output the maximum element.