АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Эерэг ба сөрөг бүхэл тоо бүхий 2 хэмжээст массивыг авч үзвэл хамгийн их нийлбэртэй тэгш өнцөгтийг олоорой.

Тэгш өнцөгтийн нийлбэр нь тухайн тэгш өнцөгт дэх бүх элементүүдийн нийлбэр юм.

Энэ бодлогонд хамгийн их нийлбэртэй дэд тэгш өнцөгтийг хамгийн дээд дэд тэгш өнцөгт гэж нэрлэе.

Жишээ нь

Дарааx массивын хамгийн дээд дэд тэгш өнцөгт нь: 

 0 -2 -7  0

 9  2 -6   2

-4  1 -4  1

-1  8  0 -2

зүүн доод буланд байгаа дэд тэгш өнцөгт:

 9  2

-4  1

-1  8

нийлбэр дүн 15 байна. 

Оролт

Эхний мөрөнд массивийн хэмжээ N (1 <= N <= 400) тоо өгөгдөнө.

Үүний дараа N*N бүхэл тоо нь хоосон зай болон мөрөөр тусгаарлагдана өгөгдөнө.

Массив дахь тоонууд [−127, 127] хооронд байна. 

Гаралт

Xамгийн дээд дэд тэгш өнцөгтийн нийлбэр байна. 

Жишээ

Оролт 1

4

 0 -2 -7  0 

 9  2 -6  2

-4  1 -4  1

-1  8  0 -2 

Гаралт 1 

15 

Оролт 2

2

1 1

1 1 

Гаралт 2

4 

Зохиогч  And Systems, LendMn software engineer Б. Жанчив