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 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 ( ) then 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 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 For all i, array[i][0] = 0

Next let us pick any two column, say p and q (with latex {n \choose 2}$. Running time is

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

Do let me know if someone have a better idea.

— Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: algorithm

This entry was posted on November 15, 2008 at 4:44 pm and is filed under algorithm, math. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

December 19, 2008 at 7:26 am |

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

December 19, 2008 at 7:34 am |

will definitely work. At each point you keep track of whether the running sum exceeds already registered sum. Answer will be 8 in this case.

December 30, 2008 at 11:45 am |

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.

December 30, 2008 at 12:17 pm |

No, according to the description, you reset the cumulative sum to zero when it goes below zero, however, at each step you should observe if it goes beyond the previously recorded maximum.

December 30, 2008 at 12:22 pm

Ok, I guess it was a bad description which misled you to believe that algorithm is wrong, I have rectified the description now.

January 23, 2009 at 4:19 am |

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.

January 23, 2009 at 4:37 am |

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

January 23, 2009 at 5:17 am |

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.

September 9, 2009 at 10:17 am |

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.

March 15, 2010 at 7:14 pm |

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

August 9, 2010 at 11:16 am |

When all numbers are negative, the sub-sequence of zero length is returned, and the sum is zero.

November 5, 2010 at 4:48 pm

When all numbers are negative, just find the largest no..

In the case of { -4 , -5 , -1 , -3 , -10 } , -1 is d ans..

November 9, 2010 at 12:33 pm |

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