Help for Bottom Up Approach


#1

int Solution::calculateMinimumHP(vector<vector > &A) {
int rows = A.size();
if(rows == 0)
{
return 0;
}

int cols = A[0].size();

int arr[rows][cols];
int ans[rows][cols];
int i,j;
for(i=0;i<rows;i++)
{
    for(j=0;j<cols;j++)
    {
        arr[i][j] = INT_MIN;
        ans[i][j] = INT_MIN;
    }
}

arr[0][0] = A[0][0];
if(arr[0][0] <= 0)
{
    ans[0][0] = abs(arr[0][0])+1;
}
else
{
    ans[0][0] = 0;
}

for(i=1;i<cols;i++)
{
    arr[0][i] = arr[0][i-1] + A[0][i];
    if(arr[0][i] < 0)
    {
        ans[0][i] = abs(arr[0][i]) + 1;
        ans[0][i] = max(ans[0][i],ans[0][i-1]);
    }
    else
    {
        ans[0][i] = ans[0][i-1];
    }
    
}

for(i=1;i<rows;i++)
{
    arr[i][0] = arr[i-1][0] + A[i][0];
    if(arr[i][0] < 0)
    {
        ans[i][0] = abs(arr[i][0]) + 1;
        ans[i][0] = max(ans[i][0],ans[i-1][0]);
    }
    else
    {
        ans[i][0] = ans[i-1][0];
    }
}


for(i=1;i<rows;i++)
{
    for(j=1;j<cols;j++)
    {
        int arr1 = arr[i-1][j] + A[i][j];
        int arr2 = arr[i][j-1] + A[i][j];
        int flag = 1;
        int ans1,ans2;
        if(arr1<0)
        {
            ans1 = abs(arr1)+1;
            ans1 = max(ans1,ans[i-1][j]);
        }
        else
        {
            ans1 = ans[i-1][j];
        }
        
        if(arr2<0)
        {
            ans2 = abs(arr2)+1;
            ans2 = max(ans2,ans[i][j-1]);
        }
        else
        {
            ans2 = ans[i][j-1];
        }
        
        if(ans1 < ans2)
        {
            ans[i][j] = ans1;
            arr[i][j] = arr1;
        }
        else if(ans1 == ans2)
        {
            ans[i][j] = ans1;
            arr[i][j] = max(arr1,arr2);
        }
        else
        {
            ans[i][j] = ans2;
            arr[i][j] = arr2;
        }
    }
}

return ans[rows-1][cols-1];

}

Giving wrong answer in case of large input. Cannot find the mistake. Can somebody help?


#2

Try this test case - 3 3 -4 -4 -4 -100 -100 10 -100 -100 10