Maximum path sum I: enumerate

18-1.c

#include<stdio.h>
#define N 15
int main() {
    int i, j, max = 0, state, total, pos;
    int a[N][N];
    for (i=0; i<N; i++)
        for (j=0; j<=i; j++)
            scanf("%d", &a[i][j]);
    for (state=0; state<(1<<(N-1)); state++) {
        total = 0;
        pos = 0;
        for (j=0; j<N; j++) {
            total += a[j][pos];
            if ((state >> j) & 1)
                ++pos;
        }
        if (total > max)
            max = total;
    }
    printf("%d\n", max);
}