Given A is the array, A[i] is the value of the element at the position i (zero-based) maxSum(i) is the function that will return the maximum of sum subarray to the position i. In other words, maxSum(i) is the answer of the problem for smaller input (array of elements from position 0 to position i).
maxSum(0) = A[0] since there is only 1 sub array (with at least 1 element).
maxSum(i) = Max(A[i], A[i] + maxSum(i-1)) makes sense because a subarray to position i must include A[i] and the maxSum(i-1) is already the best choice for the previous possible subarray combinations. So either A[i] or A[i] + maxSum(i-1) will be the maximum.
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.
Given
Ais the array,A[i]is the value of the element at the positioni(zero-based)maxSum(i)is the function that will return the maximum of sum subarray to the positioni. In other words,maxSum(i)is the answer of the problem for smaller input (array of elements from position0to positioni).maxSum(0) = A[0]since there is only 1 sub array (with at least 1 element).maxSum(i) = Max(A[i], A[i] + maxSum(i-1))makes sense because a subarray to positionimust includeA[i]and themaxSum(i-1)is already the best choice for the previous possible subarray combinations. So eitherA[i]orA[i] + maxSum(i-1)will be the maximum.Cheers
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
forloop since every maxSum(i) will end up calling maxSum(0). Thus if we go from 0 toiand 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.