CareerCup

How could it be O(n). Since you have compare each element of A with each element of B. its atleast O(mn) where m is size of A and n is Size B

Really interesting, if someone can generate m*n sums in O(n) time...

a lot of unclear questions here, which are really annoying. kind of wasting time!

go for O(n^2) soln.

We can generate the first row solution[0][i] by adding a[i] with b[0]. for subsequent rows we can just add solution[j][i] = solution[j-1][i] + (a[i]-a[i-1]). In this way we need not to hit the b array again, we are just manipulating the solution itself. Thus reducing the complexity of solution to o(n).

i think creating m*n elements can not be done in o(n) becoz each operation will take o(1) atleast

Agree, it can not be done in O(n) time. Here is algo:
1) create array C[m*n];
2) generate all sums and store them in C
3) Use count sort which has linear time to sort C in decreasing order