# C# DP sum left,right,up,down 4 directions, time O(mn), space O(mn)

• ``````public class point
{
public int left;
public int right;
public int up;
public int down;
}
public class Solution {
public int MaxKilledEnemies(char[,] grid) {
int rows=grid.GetLength(0);
int cols=grid.GetLength(1);
if(rows==0||cols==0)
return 0;
point[,] leftTopDP=new point[rows,cols];

for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
leftTopDP[i,j]=new point();
int left = (j>0?leftTopDP[i,j-1].left:0);
int up = (i>0?leftTopDP[i-1,j].up:0);
if(grid[i,j]=='E')
{leftTopDP[i,j].left=left + 1;
leftTopDP[i,j].up=up + 1;}
else if(grid[i,j]=='0')
{leftTopDP[i,j].left=left;
leftTopDP[i,j].up=up;}
else
{leftTopDP[i,j].left=0;
leftTopDP[i,j].up=0;}
}
}
for(int i=rows-1;i>=0;i--)
{
for(int j=cols-1;j>=0;j--)
{
int right=(j<cols-1?leftTopDP[i,j+1].right:0);
int bot=(i<rows-1?leftTopDP[i+1,j].down: 0);
if(grid[i,j]=='E')
{leftTopDP[i,j].right=right + 1;
leftTopDP[i,j].down=bot + 1;}
else if(grid[i,j]=='0')
{leftTopDP[i,j].right=right;
leftTopDP[i,j].down=bot;}
else
{leftTopDP[i,j].right=0;
leftTopDP[i,j].down=0;}
}
}
int max=0;
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(grid[i,j]=='0')
max=Math.Max(max,leftTopDP[i,j].left+leftTopDP[i,j].right+leftTopDP[i,j].up+leftTopDP[i,j].down);
}
}
return max;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.