Maximum Subarray sum : doubt

#1

my doubts are like:
1).does this algorithm is not like kaden’s algorithm?
2).how this is dyanmic programming like there is no overlapping sub problems?
3). it will return ans = 0 for ans aray example : arr[ ] = {-1};

#2

@archa_1712,

  1. This is indeed the kadane’s algorithm, here it is implemented with O(n) space, but it can be done in O(1) space as well.
  2. Here, ith subproblem is asking for maximum till (i-1)th subproblem, which itself would ask for (i-2)nd subproblems maximum. Also (i+1) th subproblem will ask for ith subproblem which will then ask for (i-1)th subproblem which would then again ask for (i-2)nd subproblem’s maximum. See overlapping subproblems.
  3. Yes, that is a drawback of Kadane’s algorithm, it will return 0 if all elements in array are negative. But you can have a roundabout, if array has all negative elements, multiply each element by -1, apply Kadane’s algo, now multiply the result by -1. This would give the correct answer in that case.
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.