kvtoraman's blog

Any better solution?
By kvtoraman, 14 years ago, In English

You will read the number N (1<=N<=100) than i will give you N*N numbers. I want you to find the rectangle which is has the most sum and print its sum. Input: 5 1 2 3 4 5 1 -5 -20 -40 4 -8 -7 5 6 2 -5 2 -4 -8 9 1 -5 -8 -5 2 Output: 22 Is this problem has a solution better than o(n^4) ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
14 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

There is O(n3) solution. I'm not sure that it is optimal solution, but it is easy. Let's fix the upper and the lower rows of answer (O(n2)). Let's replace each column by its sum. Now we have a sequence of integers and we have to find subsegment with maximal sum. It is a standart problem and it can be solved greedily by two pointers method (O(n)). Hint: use prefix sums.

→ Reply
»
14 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

this blog explain the algorithm (N^2+N^3)

http://ihaventyetdecided.blogspot.com/2010/10/kadanes-2d-algorithm.html

→ Reply
»
14 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

O(N^3) — http://e-maxx.ru/algo/maximum_average_segment

→ Reply
»
14 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

if you find english version give link please

→ Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

and me :)

→ Reply