PDA

View Full Version : bài quy hoạch động hay đây



theboywholived
14-06-2012, 09:54
trên một mảng 2 chiều n*m có ghi các số nguyên, tìm miền hình chữ nhật có tổng các số nguyên trong miền đó là lớn nhất.

ví dụ:

input:
1 -6 -5 6
2 -1 6 7
-1 1 1 1

output:
16

mikelhpdatke
25-07-2012, 20:39
Bài này duyệt trâu O(n^2) rồi xét (duyệt i,j với i là tọa độ góc trên trái, j là tọa độ góc dưới phải ), cách này hơi lâu với n,m lớn