What if the array consists of all negative numbers. Then the algorithm will return a zero sum which however is not correct. How do we solve this?
Kanade's Algorithm
@Siddhartha
Kadane’s Algo is used to find the maximum subarray sum. Since there is always a NULL subarray ( A subarray with no elements ) for every array , if there were all negative elements in an array then the highest sum would be obtained through the NULL subarray which would be 0 only.
However if you wish to modify your algo in case you do not wish to consider the NULL subarray , you can make another variable in which you find the maximum element of the array in the same loop. If all elements in the array were negative , you print the maximum element of the array , otherwise you print the maximum sum computed only.