Largest sum sub-sequence and sub-matrix!

Well,

I happened to bump into two old problems which I had solved sometime back. However, I never bothered to write it down anywhere which I intend to do so now.


Problem 1 : Given a sequence of n integers ( +ve and/or -ve ) find a contiguous subsequence with the largest sum. By contiguous subsequence I mean if the i-th element and j-th element of the original sequence are in the subsequence for ( i \leq j ) then \forall k, i \leq k \leq j k-th element is in the subsequence.

Example :  sequence :  1 5 -9 2 4 3 8

desired subsequence : 2 4 3 8

Problem 2 : Given a m x n matrix A, find a submatrix of A such that sum of all the elements of the submatrix is the largest amongst all possible submatrices.

Example :

1 2 -1
-3 -1 4
1 -5 -2

Desired sub matrix :

2 -1
-1 4

Solution 1 : Well, actually, solution for this is very easy and many people know about it. Still, for those who don’t know, let me describe it over here.

Initialize max_sum = 0.

You start calculating cumulative sum from the first element,at each step you store it in max_sum if it is greater than its current value. If at any point of time the cumulative sum goes below zero, store it in max_sum if it is greater than its current value, and reset cumulatvie sum to zero. Subsequently, update max_sum only if the current running sum is greater than max_sum. At the end, max_sum will give the largest sum. What about the subsequence? Well, you can keep start_index and end_index to keep track of which contiguous subsequence contributed to max_sum.

Running time is O(n) and I guess this is the best possible.


Solution 2  : Second one is a bit tricky but not too tough. In fact, we will use Solution 1 to calculate this one.

First what we do is for each row calculate cumulative sum array. That is array[i][j]  will contain sum of all element from 1 to j in the i-th  row. Time required is O(mn) For all i, array[i][0] = 0

Next let us pick any two column, say p and q (with p \leq q). Now, we will form a new array, sum_array[k] = array[k][q] - array[k][p-1]. That is, sum_array[k] will contain sum of all elements from p to q in row k.    Now, apply Solution 1 to find max_sum. Remember that indexes now will give you start_row and end_row. p and q are start_column and end_column respectively. But we did it only for two particular column. To find the submatrix having the largest sum we will have to apply it for all possible column combinations latex {n \choose 2}$. Running time is O(n^2 m)

I don’t know whether this is the best possible solution, or does there exist any solution which can achieve this in complexity better than O(n^2 m )

Do let me know if someone have a better idea.

— Saurabh Joshi

Advertisements

Tags:

13 Responses to “Largest sum sub-sequence and sub-matrix!”

  1. Dr.Sai Says:

    Will not work if {8,-7,3} is taken.

  2. Andy Says:

    According to your description of solution1, the sum is registered only when the cumulative sum goes below zero. This does not happen in Dr. Sai’s sequence. So your algo gives the max sum as 4.

  3. Debjit Says:

    Just a minor suggestion for the submatrix problem. At the end when you create all possible combinations of columns. The number of such combinations is not 2^n since the restriction that p<q will eliminate most combinations. For example for 3 columns which we can name column a, b and c the combinations will only be:

    p=a, q=b
    p=a, q=c
    p=b, q=c

    The remaining combinations need not be explored.

    • Saurabh Joshi Says:

      where have I written 2^n?, please read carefully I have written number of combinations as nC2 or {n Choose 2}, if you are not familiar with mathematical notation then following might help
      nC2 = n(n-1)/2

  4. Debjit Says:

    Hmmm… it seems the LateX formatting is a bit off on my mozilla browser. The C is not at all visible. Which is why I added the comment. nC2 is perfectly fine. Since I am now commenting on latex :), the following line also does not display correctly on my browser:

    “say p and q (with $latex p \leq q)”.

    P.S. Although combinatorics was not my favorite topic in school or college, I do know what nC2 means :P.

  5. anonymus Says:

    after finding the sub_array[k] for each suck k rows we can use the solution of problem1 to find the maximum subvector in sub_array[k] by which we can know what are the rows(k2 and k5) in which the required elements lie …
    p q
    —|—–|–
    k2 –|—–|–
    –|—–|–
    k5 –|—–|—

    but we also need to find the columns(p,q) which will lead us to maximum subarray..

    so for finding p and q should i maintain k*(p+q) variables or is there any method by which i can compute the same in less space.

  6. S Says:

    What about {-4,-5,-1,-3,-10}?

  7. Saurabh Joshi Says:

    Nope it is the subsequence of zero length and the answer is zero

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: