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) ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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.
this blog explain the algorithm (N^2+N^3)
http://ihaventyetdecided.blogspot.com/2010/10/kadanes-2d-algorithm.html
O(N^3) — http://e-maxx.ru/algo/maximum_average_segment
Thanks but any english version?
I sudgest you to use google translate or look for another solution in the Internet. Or you can learn russian :)
if you find english version give link please
and me :)