Counting Maximum Apples

A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner.

Code (O(m*n) time, O(m*n) space):

#include<iostream>
#include<stack>
using namespace std;
 
int path(int (*array)[4],int row)
{
        int **aux = new int *[row];
        for(int i=0;i<row;++i)
                aux[i]=new int[4]();
        
        aux[0][0] = array[0][0];
        for(int i=0,j=1;j<4;++j)
                aux[i][j] = aux[i][j-1] + array[i][j];
        
        for(int i=1,j=0;i<row;++i)
                aux[i][j] = aux[i-1][j] + array[i][j];
        
        for(int i=1;i<row;++i)
        {
                for(int j=1;j<4;++j)
                {
                        aux[i][j] = array[i][j] + std::max(aux[i-1][j],aux[i][j-1]);
                }
        }
        
        stack<string> st;
        
        st.push("At Destination");
        int i,j;
        for(i=row-1,j=3;i>0 && j>0;)
        {
                if(aux[i][j] - array[i][j] == aux[i-1][j])
                {
                        st.push("go down");
                        i--;
                }
                else
                {
                        st.push("go right");
                        j--;
                }
        }
        if(i==0)
                while(j--)
                        st.push("go right");
        if(j==0)
                while(i--)
                        st.push("go down");
        
        cout<<"At Source, now..\n";
        while(!st.empty())
        {
                cout<<st.top()<<"\n";
                st.pop();
        }
        return aux[row-1][3];
        
}
int main()
{
        int array[3][4]={{1,2,3,4},
                                         {1,1,1,1}, 
                                         {9,9,9,9}
                                        };
                
        int total = path(array,3);
        cout<<"Total:"<<total<<endl;
        return 0;
}