kvtoraman's blog

Any better solution?
By kvtoraman, 12 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

»
12 years ago, # |
  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
»
12 years ago, # |
  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
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Thanks but any english version?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I sudgest you to use google translate or look for another solution in the Internet. Or you can learn russian :)

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

if you find english version give link please

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

and me :)

→ Reply