I’m doing the Philosopher’s Stone problem but I’m getting time limit exceeded. Also it says I’m using 4500M of memory which is a lot compared to solutions for some other problems. I don’t know how to do Big O analysis and am new to this, I’d appreciate if someone would look at my code.
int i = 0, maximum = 0, j = 0,junk = 0;
Scanner in = new Scanner(System.in);
int cases = in.nextInt();
for (int cas = 0; cas <cases; cas++)
{
int h = in.nextInt();
int w = in.nextInt();
int[][] data = new int[h][w];
int[][] res = new int[h][w];
for (i = 0; i < h; i++)
{
for (j = 0; j < w; j++)
data [i][j] = in.nextInt();
}
res [h-1] = data[h-1];
if (w == 1)
{
int ans = 0;
for (i = 0; i < h; i++)
ans = ans + data[i][0];
System.out.println (ans);
continue;
}
if (h == 1)
{
maximum = -1;
for (int entry = 0; entry < w; entry++)
{
junk = data[0][i];
if (junk > maximum)
maximum = junk;
}
System.out.println(maximum);
continue;
}
//loop through each row starting with the second from the bottom and going up
for (i= h - 2; i > -1; i--)
{
res [i][0] = Math.max(res[i+1][0], res[1+1][1]) + data [i][0];
res [i][w-1] = Math.max(res[i+1][w-2], res[i+1][w-1]) + data [i][w-1];
for (j = 1; j < w-1; j++)
res [i][j] = Math.max(Math.max(res[i+1][j],res[i+1][j-1]),res[i+1][j+1]) + data [i][j];
}
maximum = -1;
for (i = 0; i < w; i++)
{
junk = res[0][i];
if (junk > maximum)
maximum = junk;
}
System.out.println (maximum);
}