It is but that recursive can be converted to one for loop since every maxSum(i) will end up calling maxSum(0). Thus if we go from 0 to i and calculate and store the results (or at least the last result) the time complexity of the algorithm will be linear O(n). Brute force on the other hand, we have to find all the subarray and calculate the sum for each and then find the max of the results.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Does this imply recursion? How is this better than the brute force one? Thanks for your reply.
It is but that recursive can be converted to one
for
loop since every maxSum(i) will end up calling maxSum(0). Thus if we go from 0 toi
and calculate and store the results (or at least the last result) the time complexity of the algorithm will be linearO(n)
. Brute force on the other hand, we have to find all the subarray and calculate the sum for each and then find the max of the results.