``` #include<iostream> using namespace std; const int n = 5; int path[n][n]; int maxAdd(int arr[][n],int n) { int maxAdd[n][n]; for(int i = 0; i < n; i++) { maxAdd[n - 1][i] = arr[n - 1][i]; } for(int i = n - 2; i >= 0; i--) { for(int j = 0; j <= i; j++) { maxAdd[i][j] = arr[i][j] + max(maxAdd[i + 1][j],maxAdd[i + 1][j + 1]); if(maxAdd[i + 1][j] >= maxAdd[i + 1][j + 1])path[i][j] = j + 1; else path[i][j] = j + 2; } } return maxAdd[0][0]; } int main() { int d[n][n] = {{8},{12,6},{3,9,4},{6,5,7,8},{1,2,3,4,5}}; cout<<maxAdd(d,n)<<endl<<endl; for(int i = 0; i < n; i++) { for(int j = 0; j < i + 1; j++) { if(path[i][j] == 0)cout<<0<<" "; else cout<<path[i][j]<<" "; } cout<<endl; } return 0; } ```