Maximum triangle path sum: Difference between revisions
Content added Content deleted
(Added zkl) |
No edit summary |
||
Line 80: | Line 80: | ||
<pre> 1320 |
<pre> 1320 |
||
</pre> |
</pre> |
||
=={{header|C++}}== |
|||
{{trans|Ada}} |
|||
<lang cpp> |
|||
#include <iostream> |
|||
int main( int argc, char* argv[] ) |
|||
{ |
|||
int triangle[] = |
|||
{ |
|||
55, |
|||
94, 48, |
|||
95, 30, 96, |
|||
77, 71, 26, 67, |
|||
97, 13, 76, 38, 45, |
|||
7, 36, 79, 16, 37, 68, |
|||
48, 7, 9, 18, 70, 26, 6, |
|||
18, 72, 79, 46, 59, 79, 29, 90, |
|||
20, 76, 87, 11, 32, 7, 7, 49, 18, |
|||
27, 83, 58, 35, 71, 11, 25, 57, 29, 85, |
|||
14, 64, 36, 96, 27, 11, 58, 56, 92, 18, 55, |
|||
2, 90, 3, 60, 48, 49, 41, 46, 33, 36, 47, 23, |
|||
92, 50, 48, 2, 36, 59, 42, 79, 72, 20, 82, 77, 42, |
|||
56, 78, 38, 80, 39, 75, 2, 71, 66, 66, 1, 3, 55, 72, |
|||
44, 25, 67, 84, 71, 67, 11, 61, 40, 57, 58, 89, 40, 56, 36, |
|||
85, 32, 25, 85, 57, 48, 84, 35, 47, 62, 17, 1, 1, 99, 89, 52, |
|||
6, 71, 28, 75, 94, 48, 37, 10, 23, 51, 6, 48, 53, 18, 74, 98, 15, |
|||
27, 2, 92, 23, 8, 71, 76, 84, 15, 52, 92, 63, 81, 10, 44, 10, 69, 93 |
|||
}; |
|||
int last = sizeof( triangle ) / sizeof( int ), |
|||
tn = 1; |
|||
while( ( tn * ( tn + 1 ) / 2 ) < last ) tn += 1; |
|||
last--; |
|||
for( int n = tn; n >= 2; n-- ) |
|||
{ |
|||
for( int i = 2; i <= n; i++ ) |
|||
{ |
|||
triangle[last - n] = triangle[last - n] + std::max(triangle[last - 1], triangle[last]); |
|||
last--; |
|||
} |
|||
last--; |
|||
} |
|||
std::cout << "Maximum total: " << triangle[0] << "\n\n"; |
|||
return system( "pause" ); |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre>Maximum total: 1320</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |