7
$\begingroup$

I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms".

it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], A[i+1] , ... , A[j] in given array A[1] , ... , A[n].

The exercise is about developing linear-time algorithm to solve this using a following idea, (f.y.i. A[1 ,... , j] means A[1] , A[2] , ... , A[j] )

Knowing a maximum sub-array of A[1, ... , j], extend the answer to find a maximum sub-array ending at index j+1 by using the following observation: a maximum sub-array of A[1, ... , j+1] is either a maximum sub-array of A[1,...,j] or a sub-array A[i,...,j+1], for some 1 <= i <= j+1. Determine a maximum sub- array of the form A[i,...,j+1] in constant time based on knowing a maximum sub- array ending at index j." .

People said that this solution is actually Kadane's algorithm, which is relatively a simple algorithm stated on Wikipedia (I'm really sorry that you have to move to another site. but it explains better than I do.)

However, Kadane's Algorithm deals with only a sub-array that ends at exactly j. but above idea says I should use maximum sub-array of A[1, ... , j] and we can't guaranteed that this sub-array should end with j. Because I think this two algorithm is quite different.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

Suppose $A[1..N]$ is your array for which you want to find maximum sum sub-array. Construct $B[1..N]$ such that $B[j]=max (\sum A[k] \mid k \le j,k \ge i)$ ($i$ is some starting index for which B[j] is maximum). So it boils down to $B[j]=max(B[j-1]+A[j],A[j])$ (here I am assuming that empty sub-array isn't allowed in answer). And then find the maximum $B[j]$ for all $j \in [1..N]$. Now this can be done in constant space since we only need result of the previous iteration( for $j$ we need only $B[j-1]$) and the maximum sub-array sum which has occurred till now. Now compare these two ideas and you will get you answer.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Thank you for your answer. I can understand your answer and I learned really a lot from it !! i want to ask some questions. First, Is your answer equivalent to Kadane's Algorithm? I think these two are not same and yours is simpler than Kanade's. Second, Idea I mentioned above said that i use "maximum sub-array of A[1, ... j]"(Bold line on my question). Is there no problem to consider your B[j] as this sub-array? $\endgroup$
    – Lee Young joo
    Commented Jun 23, 2015 at 5:59
  • 2
    $\begingroup$ The second idea which used constant space is Kadane's Algorithm. Maximum sum subarray for $A[1..j]$ is not $B[j]$ but $max(B[k] \mid k \le j)$ . $B[j]$ is only max subarray sum ending at $j$. $\endgroup$
    – donkey
    Commented Jun 23, 2015 at 6:05
  • 1
    $\begingroup$ I am sorry to keep bothering you. But I have one more question. I think yours doesn't take advantage of max(B[k]∣k≤j) but only B[j]. So, isn't your algorithm(and Kadane's one) using idea above i mentioned? $\endgroup$
    – Lee Young joo
    Commented Jun 23, 2015 at 6:20
  • 1
    $\begingroup$ The first algorithm that I used doesn't take advantage of this but the second one (Kadane's algorithm) has this stored in the form of max_so_far in the wiki page. $\endgroup$
    – donkey
    Commented Jun 23, 2015 at 6:25
  • $\begingroup$ It is clear to me now! Thank you for your kind explanation!!! $\endgroup$
    – Lee Young joo
    Commented Jun 23, 2015 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.