I was solving UVa 10755 — Garbage Heap abridged statement : Given values in 3D space, compute a 3D rectangle with maximum sum. The 2D version is given a matrix, find a submatrix with maximum sum which can be easily done by using 2D Kadane algorithm. But the 3D version of it seems quite difficult, I solved it using a rather different approach:

First storing the 3D rectangle sums starting from (0, 0, 0) to (i, j, k):

    for (int i=0;i<A;++i) for (int j=0;j<B;++j) for (int k=0;k<C;++k) {
      long long g; cin>>g;
      if (i>0) g+=m[i-1][j][k];
      if (j>0) g+=m[i][j-1][k];
      if (k>0) g+=m[i][j][k-1];
      if (i>0 && j>0) g-=m[i-1][j-1][k];
      if (j>0 && k>0) g-=m[i][j-1][k-1];
      if (i>0 && k>0) g-=m[i-1][j][k-1];
      if (i>0 && j>0 && k>0) g+=m[i-1][j-1][k-1];
      m[i][j][k]=g;
    }

Then, iterating over all the values in the array and updating max:

for (int i=0;i<A;++i) for (int j=0;j<B;++j) for (int k=0;k<C;++k) 
    for (int i1=i;i1<A;++i1) for (int j1=j;j1<B;++j1) for (int k1=k;k1<C;++k1)  {
      long long s = m[i1][j1][k1];
      if (i>0) s-=m[i-1][j1][k1];
      if (j>0) s-=m[i1][j-1][k1];
      if (k>0) s-=m[i1][j1][k-1];
      if (i>0 && j>0) s+=m[i-1][j-1][k1];
      if (j>0 && k>0) s+=m[i1][j-1][k-1];
      if (i>0 && k>0) s+=m[i-1][j1][k-1];
      if (i>0 && j>0 && k>0) s-=m[i-1][j-1][k-1];
      if (s>max_sum) max_sum = s;
    }

max_sum will be the answer, but the time complexity is O(n⁶) which I believe could be reduced by first applying 2D Kadane over the 2D space and 1D kadane for the remaining dimension, but I'm not sure on how to do that, if anyone's solved this problem, could you hint me on the right direction Thanks!