View Code of Problem 65

#include<stdio.h>
#include<math.h>
int max(int a,int b)
{
	if(a>b)
	 return a;
	else
	return b;
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
  	int n;
  	scanf("%d",&n);
  	int map[n][n];
  	int i,j,x;
  	for(i=0;i<n;i++)
  	{
  		for(j=0;j<=i;j++)
  		{
  		  scanf("%d",&map[i][j]);  
  	    }
  	    for(j=i+1;j<n;j++)
  	      map[i][j]=0;
	}
	for(i=1;i<n;i++)
	{
		for(j=1;j<i;j++)
		{
			map[i][j]=max(map[i][j]+map[i-1][j-1],map[i][j]+map[i-1][j]);
		}
		map[i][0]=map[i-1][0]+map[i][0];
		map[i][i]=map[i-1][i-1]+map[i][i];
	}
	int max=0;
	for(i=1;i<n;i++)
	{
		if(map[n-1][max]<map[n-1][i])
		  max=i;
	}
//	for(i=0;i<n;i++)
//	{
//		for(j=0;j<=i;j++)
//		 printf("%d ",map[i][j]);
//		printf("\n");
//	}
	printf("%d\n",map[n-1][max]);
	
  }
}