ll res = -oo;
for(int k=1; k<=n; k++)
for(int i=1; i<=n-k+1; i++)
for(int j=1; j<=n-k+1; j++)
{
f[i][j][k] = f[i][j][k - 1] + a[i + k - 1] * b[j + k - 1];
res = max(res, f[i][j][k]);
}
cout << res;
ll res = -oo;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int k=1; k<=n; k++)
{
if(k + i > n || k + j > n) break;
f[i][j][k] = f[i][j][k - 1] + a[i + k - 1] * b[j + k - 1];
res = max(res, f[i][j][k]);
}
cout << res;
These code seem not to be differ too much but execution time have much differ. Example in case n = 500, code1 run in 3103ms but code 2 run only 789ms. What is the reason ? Pls explain to me. Thanks.