Блог пользователя kvtoraman

Any better solution?
Автор kvtoraman, 12 лет назад, По-английски

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) ?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    Thanks but any english version?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

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

      → Ответить
»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

if you find english version give link please

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

and me :)

→ Ответить