algorithm - Maximum sum in a torus -


i trying solve following dynamic programming question on uva online judge:

a grid wraps both horizontally , vertically called torus. given torus each cell contains integer, determine sub-rectangle largest sum. sum of sub-rectangle sum of elements in rectangle. grid below shows torus maximum sub-rectangle has been shaded.

image of torus

we know there exists similar , simpler problem: maximal sub-rectangle problem grid canot wrap. simpler variant, can first take cumulative of each row , apply kadane's algorithm in 2 for-loops solve problem. problem, impossible since grid can wrap around.

i have headstart on problem mirroring matrix 4 times simulate rotation of matrix. however, dynamic programming related problems, have formulate recurrence relation. not know how formulate recurrence problem. please advise me?

edit:

i tried using modified kadane's algorithm search largest rectangle of @ least size 1. however, still not getting right answer. reference, code listed below: 

#include <cstdio> #include <algorithm> #include <list> using namespace std;  int main() {     int cc,r,c,r,c,inf = 9999;     scanf("%d",&cc);     while(cc--) {         scanf("%d",&r);         c = r;         r = c = 2 * r;         int l[r][c], sum[r+1][c];         fill_n(sum[0],c,0);          for(int = 0; < r; i++) {             for(int j = 0; j < c; j++) {                 scanf("%d",&l[i][j]);                 sum[i+1][j] = l[i][j];                 sum[i+1][c+j] = l[i][j];                 sum[r+i+1][j] = l[i][j];                 sum[r+i+1][c+j] = l[i][j];             }         }         for(int = 0; < c; i++) {             for(int j = 1; j < r+1; j++) {                 sum[j][i] += sum[j-1][i];             }         }         int g_max = -inf;         for(int = 0; < r; i++) {             for(int j = i+1; j < i+r+1; j++) {                 int t_max = sum[j][0]-sum[i][0], s = sum[j][0]-sum[i][0], l = 1, lo = 0, hi = 0;                 g_max = max(g_max,t_max);                 for(int k = l; k < c; k++) {                     s += (sum[j][k]-sum[i][k])-(sum[j][k-l]-sum[i][k-l]);                     t_max = max(t_max+(sum[j][k]-sum[i][k]),s);                     if(t_max > g_max) {                         g_max = t_max;                         lo = k - l - 1;                         hi = k;                         if(hi - lo == c-1) break;                     }                 }             }         }         printf("%d\n",g_max);     }     return 0; }

given test case:

1 5 1 -1 0 0 -4 2 3 -2 -3 2 4 1 -1 5 0 3 -2 1 -3 2 -3 2 4 1 -4

the grid in test case shown above. answer should 15. getting 24. not sure wrong algorithm since implemented kadane's algo stackoverflow answer. able me?


Comments

Post a Comment

Popular posts from this blog

php - How to add and update images or image url in Volusion using Volusion API -

actually have store importing products store product data insert , update image or image url not insert , update. this xml code name datapro.txt. <products_joined> <productcode>3710_012t</productcode> <vendor_partno>eah5450silent/di/1gd3(lp)</vendor_partno> <productname>test product ta</productname> <hideproduct>n</hideproduct> <stockstatus>20</stockstatus> <lastmodified>1/5/2016 10:25:00 am</lastmodified> <lastmodby>2</lastmodby> <productweight>0.9</productweight> <productprice>100</productprice> <productmanufacturer>asus tek</productmanufacturer> <vendor_price>32.69</vendor_price> <numproductssharingstock>0</numproductssharingstock> <categoryids>107</categoryids> <producturl>http://tebkq.mvlce.servertrust.com/productdetails.asp?productcode=3710_012t</producturl...
Read more

Laravel mail error `Swift_TransportException in StreamBuffer.php line 269: Connection could not be established with host smtp.gmail.com [ #0]` -

i developing website contact-us page guest users can send me email using gmail . anytime try send mail using contact-us form, error swift_transportexception in streambuffer.php line 269: connection not established host smtp.gmail.com [ #0] this mail.php return [ 'driver' => env('mail_driver', 'smtp'), 'host' => env('mail_host', 'smtp.gmail.com'), 'port' => 587, 'from' => ['address' => '', 'name' => ''], 'encryption' => env('mail_encryption', 'tls'), 'username' => env('mail_username'), 'password' => env(mail_password), 'sendmail' => '/usr/sbin/sendmail -bs', 'pretend' => env('mail_pretend', false), ]; this .env mail_driver=smtp mail_host=smtp.gmail.com mail_port=587 mail_username=afecjaped@gmail.com mail_password=********...
Read more

c# SetCompatibleTextRenderingDefault must be called before the first -

i tried search exception couldn't find solution on case i'am using code below invoke .net application : assembly assem = assembly.load(data); methodinfo method = assem.entrypoint; var o = activator.createinstance(method.declaringtype); method.invoke(o, null); the application invoked has form , in entrypoint of application : [stathread] static void main() { application.enablevisualstyles(); application.setcompatibletextrenderingdefault(false); //exception application.run(new form1()); } setcompatibletextrenderingdefault must called before first iwin32window object created in application. edit : assembly = assembly.load(data); methodinfo method = a.gettype().getmethod("start"); var o = activator.createinstance(method.declaringtype); method.invoke(o, null); you should create new method skips initialization...
Read more