Skip to content

Instantly share code, notes, and snippets.

@bojieli
Created October 27, 2014 12:35
Show Gist options
  • Save bojieli/781823da3317cc697543 to your computer and use it in GitHub Desktop.
Save bojieli/781823da3317cc697543 to your computer and use it in GitHub Desktop.
Maximum path sum I: enumerate
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment