warning: at the time this post was shared, contest was being held. if you spot any similarity between live contest questions and this post, feel free to remove it, though author of this post has not intended any cheating, yet.
Codechef SUMTRIAN - Sums in a triangle: SUMTRIAN Problem - CodeChef
Codechef SUMTRIAN - Sums in a triangle editorial: need guidance in sums in triangle problem - general - CodeChef Discuss
Codechef SUMTRIAN - Sums in a triangle solution: http://ideone.com/1Qb7Ce
#include <iostream>
#include <cstdio>
using namespace std;
long long int a[105][105]={0};
int main() {
int n, m;
scanf("%d", &n);
while(n--) {
scanf("%d", &m);
for(int i=0; i<m; i++) for(int j=0; j<=i; j++) scanf("%lld", &a[i][j]);
for(int i=m-2; i>=0; i--) for(int j=i; j>=0; j--) {
if(a[i+1][j+1]>a[i+1][j]) a[i][j]+=a[i+1][j+1];
else a[i][j]+=a[i+1][j];
}
printf("%lld\n", a[0][0]);
for(int i=0; i<105; i++) for(int j=0; j<105; j++) a[i][j]=0;
}
return 0;
}
note: use dp(dynamic programming), start from the right bottom of the triangle, and the loop from right to left. for each specific cell(a[i][j]
), try to find which cell, directly below(a[i+1][j]
) or directly below and one place to the right(a[i+1][j+1]
), is bigger to add to current one(a[i][j]
). when all looping and summing up finishes just print the value of top cell(a[0][0]
), because that cell will represent the maximum possible sum of triangle.