Hi Sir, I am not able to understand the Kadane’s Algo properly, I have this confusion that if all the elements of the array are negative, in that case, we won’t be able to calculate the sum.
Maximum Subarray Sum Using Kadane's Algo
Hi Shobhit. Kadane’s algo is actually very simple,and takes time complexity of O(n), compared to Brute force approach which takes O(n^2).
It won’t make a difference if all the elements in the array are negative, it would return the sub-array with maximum sum present, just like it would in the case of positive numbers. For eg. in array {-3,-1,-2} -> first we check for -3, save it and then while traversing towards next element, we’ll select either (-1)+(-3) which is (-4) or -1 and will have -1 saved(for that position) since it is greater. Now when we reach -2. the subarray would either be -2 or sum with one less position ( i.e (-2)+)(-1)= -3), or sum with one less position again (-3 + -1+ -2), which is -6. So, out of all saved sums, -1 is the largest, hence it is the answer.
@Shobhit-Sharma-1473370192798371 hey shobit in that case you can refer this line of code Code link .