Question

Salut! Imi poate scrie cineva un cod cum as putea afla submatricea de suma maxima dintr o matrice? c++

Answer 1

salut! complexitatea este (n*m)^2 unde n si m sunt nr de linii respectiv coloane. Se folosesc sume partiale pe matricea respectiva. Ai cod mai jos:

cin>>n>>m;

   for(i=1;i<=n;i++)

       for(j=1;j<=m;j++)

   {

      cin>>nr;

       s[i][j]=nr+s[i][j-1]+s[i-1][j]-s[i-1][j-1];  // sume partiale

   }

   for(x1=1;x1<=n;x1++)  // iau fiecare colt din matrice

       for(y1=1;y1<=m;y1++)

           for(x2=x1;x2<=n;x2++)

               for(y2=y1;y2<=m;y2++)

   {

       S=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];  // suma submatricei

       if(S>maxim)

       {

               maxim=S;

               i1=x1; i2=x2;

               j1=y1; j2=y2;

       }

   }

coroana, te rog? e ceva de scris