самый длинный путь в матрице

Question

Учитывая матрицу NXN Matrix [N] [N] натуральных чисел.Матрица ячейки [r] [c] имеет только три возможных хода.

1. Матрица [r + 1] [c]

2. Матрица [r + 1] [c-1]

3. Матрица [r + 1] [c + 1]

Начиная с любого столбцав строке 0 верните наибольшую сумму из всех путей до строки N-1.

мой код работает нормально для одного теста, но для нескольких тестов он дает неправильный ответ.В основной функции кода я передаю двумерный массив и количество элементов в массиве в качестве аргументов

int findSum(int a[][100],int n)
{
    int i,j;
    for(i=1;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            int x=a[i][j];
            if(j==0)
            {
                a[i][j]=max(a[i-1][j],a[i-1][j+1])+x;
            }
            if(j==n-1)
            {
                a[i][j]=max(a[i-1][j],a[i-1][j-1])+x;
            }
            else
            {
                a[i][j]=max(a[i-1][j],max(a[i-1][j-1],a[i-1][j+1]))+x;
            }
        }
    }
    int maxm=a[n-1][0];
    for(j=0;j<n;j++)
    {
        if(a[n-1][j]>maxm)
           maxm=a[n-1][j];
    }
    return maxm;
}

Массив берется в качестве ввода от пользователя

while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
               scanf("%d",&a[i][j]);
        }
        int num=findSum(a,n);
        printf("%d\n",num);
    }

Для ввода: 23 5 6 7 7 6 5 7 6 5 3 7 3 2 4 1 5 6 8 9 Ваш вывод: 20 32 ожидаемый результат должен быть 19 для второго случая

Answer 1

Используйте оператор if-else-if вместо кратного оператора if.

if(j==0)
{
     a[i][j] += max(a[i-1][j],a[i-1][j+1]);
}
else if(j==n-1)
{
     a[i][j] += max(a[i-1][j],a[i-1][j-1]);
}
else
{
     a[i][j] += max(a[i-1][j],max(a[i-1][j-1],a[i-1][j+1]));
}