CareerCup

Part 1 can be solved by using simple dynamic programming technique. It's in Mark Allen Weiss text book.

The second problem can be solved in variety of ways and there is O(m*n) algo to solve the second question too. It is same as this problem CTGAME in spoj online judge

@above ..cn u discuss d 2nd question's solution..

@above: Please explain the solution for the second part...with example..

for 2:

fist think about how to find the largest rectangle in a histogram. (search HISTOGRA in spoj)

then think about how to extend the 1D largest rectangle thing into a 2D scenario. (search CTGAME in spoj)


other problems that you can relate to this question:
1. given an array, find the largest sum over a sliding window
2. given an matrix filled with negative or positive values, find the rectangle with the maximum sum of elements within