Finding a duplicated integer in a given array, O(n) time and O(1) space

Finding a duplicated integer. Given a read-only array of n integers between
1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use
only O(1) space. Hint: equivalent to finding a loop in a singly linked
structure.

http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare


http://www.mitbbs.com/article_t1/JobHunting/31942529_0_1.html
IANGLE PUZZLE
By starting at the top of the triangle and moving to adjacent numbers on the
row below, the maximum total from top to bottom is 27..
5

9 6

4 6 8

0 7 1 5

I.e. 5 + 9 + 6 + 7 = 27.
Write a program in a language of your choice to find the maximum total from
top to bottom in triangle.txt, a text file containing a triangle with 100
rows.
download traiangle.txt in http://www.yodle.com/downloads/puzzles/triangle.txt

who can fix this problem? It is very difficult. Please post your answer

Project Euler Problem 18 & 67

work bottom-up, greedy

从倒数第二行开始。每个数字和下一行的两个数字相加。选较大的值存。然后再上一行
5
9 6
4 6 8
0 7 1 5

倒数第二行的4和下一行它能reach的两个值0和7相加。取较大的4+7=11。
倒数第二行的6和下一行它能reach的两个值7和1相加。取较大的6+7=13。

三角形变为

5
9 6
11 13 13

再变为

5
22 19

再变为

27

最大值