-
Notifications
You must be signed in to change notification settings - Fork 0
/
873. Length of Longest Fibonacci Subsequence.py
41 lines (33 loc) · 9.79 KB
/
873. Length of Longest Fibonacci Subsequence.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
def lenLongestFibSubseq(self, A):
"""
:type A: List[int]
:rtype: int
"""
# result = 0
# num = len(A)
# for i in range(num-2):
# for j in range(i+1,num-1):
# a,b = A[i],A[j]
# count = 2
# while a+b in A:###while loop 真的是个好东西，它会一直检查下去的。
# count +=1
# a, b = b, a+b
# result = max(result,count)
# return result if num>=3 else 0
s = set(A)
result = 0
num = len(A)
for i in range(num-2):
for j in range(i+1,num-1):
a,b = A[i],A[j]
count = 2
while a+b in s:###while loop 真的是个好东西，它会一直检查下去的。
count +=1
a,b = b,a+b
result = max(result,count)
return result if num>=3 else 0
B=[2,3,5,6,8,10,13,21,34,36,41,48,53,55,59,62,71,76,77,79,82,85,88,89,90,92,94,100,107,127,135,144,151,155,170,174,175,177,178,213,229,233,254,258,262,265,266,285,302,364,377,417,428,431,440,463,477,577,593,679,685,686,705,706,748,779,941,957,1096,1114,1116,1145,1146,1211,1256,1518,1550,1775,1800,1801,1850,1852,1959,2035,2459,2507,2871,2914,2917,2995,2998,3170,3291,3977,4057,4646,4714,4718,4845,4850,5129,5326,6436,6564,7517,7628,7635,7840,7848,8299,8617,10413,10621,12163,12342,12353,12685,12698,13428,13943,16849,17185,19680,19970,19988,20525,20546,21727,27262,27806,31843,32312,32341,33210,33244,35155,44111,44991,51523,52282,52329,53735,53790,56882,71373,72797,83366,84594,84670,86945,87034,92037,115484,117788,134889,136876,136999,140680,140824,148919,186857,190585,218255,221470,221669,227625,227858,240956,308373,353144,358346,358668,368305,368682,389875,571399,579816,595930,596540,630831,924543,938162,964235,965222,1205687,1495942,1517978,1560165,1561762,2420485,2456140,2524400,2526984,3504731,3831446,3916427,3974118,4002090,4084565,4509148,4559662,5348874,6336912,6430258,6608965,9639665,10166759,10253339,10693530,11791075,12573186,15167813,15784914,16590251,17242347,17302495,17453914,17960008,18395525,22466942,24130340,24814929,25055001,26147497,26843590,28600458,29632548,30143678,31619589,33316575,33324705,33929823,34491960,36660636,37023576,38566553,39005554,39161190,39751927,41424002,42470682,43433841,44450796,44603755,49542081,51204445,53280589,54160086,54354920,55016892,55350758,55688772,58155893,58213146,59293127,59410084,59813293,61358327,61752966,62585447,62856338,63699870,64127901,69342941,70257310,71644382,71860863,72963580,73173493,73923256,74629208,75078994,77252482,78358668,78535889,78780034,81857328,84163423,87339761,91189193,91410480,92243700,92322190,94442269,94942054,95339444,96904829,97226016,101168719,101460910,103560098,104051625,105213329,105444809,105605074,108051430,108206549,108487404,109069670,112782136,113823258,114556687,114581094,115697128,115728631,116531844,116822945,118045433,120540898,120734292,122808639,122871447,123788160,125346258,125991846,128161209,129711782,131971057,132477044,133434449,133844372,138298540,140182550,140586965,142236358,143225417,143632237,144897975,145478161,147313205,148615559,149473046,151964835,153558532,153607150,155499266,155580401,157193429,157808818,159054382,164746944,166422752,166453690,166629517,166862696,167077932,167222203,168161720,168284247,168766097,169628320,170904526,172726498,173212714,173821355,176089878,177794179,178319632,179820995,179869583,180600370,180992422,181798638,182195168,182612467,183922607,185263935,186812612,189278070,191371379,191529936,193075051,193307317,193684463,193939438,195156533,195484292,198067435,199822054,200154734,200719334,203128800,203616626,206171095,206777056,207983486,208360317,210547395,212506844,213478317,214944805,217741483,219020281,220542940,220783823,224112195,225746076,226065075,226905308,229389005,229863650,230668040,231194337,231764785,236327265,237147722,238624580,239949153,241981840,242845440,243892913,244017096,244160600,245127129,246576704,246610966,248887329,254886138,257421166,257841025,258468561,262629345,262665495,262762914,263027728,264229836,266123118,267667749,268874526,271003053,272371305,272904197,273299604,276890798,277819526,278784802,281035594,281658085,282958499,283402734,284239493,284773090,285026534,285515483,286009375,289353808,289428658,290983106,291017166,291695203,293068921,293084175,293414793,294445840,298140488,298222421,298665843,299614676,300124272,300315863,301669670,302294777,303354591,303708275,304306582,304924680,308204204,310166858,310727680,310896278,311550974,311693559,312298447,312773231,314249724,318855480,322624549,325306349,331678071,332532249,333186240,334045554,334295613,334752625,335019247,337516550,338405759,338996818,339763698,339899334,340132342,340795510,341116555,343424680,343611022,345417769,346347365,348097870,348261260,348776328,349500598,351418413,352664533,353408396,354449350,355755401,356796223,357460525,358292157,358416754,360011320,360079910,362145391,363234555,363438822,364928424,365024379,365538282,367614899,372971424,373348772,375585767,376890463,377564515,378912622,380189427,380659236,380880228,382703926,382995165,383519034,385283571,387825679,389058508,389313630,389910494,390653935,392445625,393487349,393958446,395245624,395492856,397431804,398082099,400598455,400686579,403253702,403678723,405222823,405317212,407157192,408277694,412438744,413775940,415016507,415219991,418698794,423298204,423350581,425261493,426156524,426235865,427575935,428028330,430431796,432935904,433227271,433913255,434021017,434683477,435438804,437858207,438668874,438683619,439498831,439718290,443006180,446529542,449002765,450536872,452401398,453418334,454118900,455726329,456232318,456603378,458138179,459507264,460408329,461627484,461964842,464332703,464497564,466138859,467861035,468890929,469940202,470026554,472336404,472400093,472878399,473938566,474891699,475113346,476869200,477737466,477828507,477878434,480761205,481495011,482439667,485433478,487641801,488183219,489851845,491410871,493005254,493169116,494609881,499506408,502056317,502844009,503290103,505822061,507485567,508336407,511561764,511579408,515699165,517225501,518133008,518226911,519107220,520442400,520914712,525798712,527046372,527971816,530872751,532041816,533871877,534360006,536789796,537599343,539693765,539724460,541541070,541588961,542369991,544413729,546150435,546443734,547350265,548655173,549450196,550298282,551039142,555884301,555891567,559161289,561740141,561941178,562401959,563386462,564549841,566768771,567691477,569176194,569580314,575949890,578198155,578982027,580218740,581004033,583472360,585199059,585792484,585898907,586427773,590038877,590057018,590238769,590468380,590825839,591254539,591818188,592060089,593049903,597414549,598884830,599763447,601916233,602224485,603031916,603272640,603461240,604941229,605895944,606322194,608636231,612338014,615208238,616018077,616176033,617361022,618759805,620050821,620164443,622561882,626289692,626880004,629621957,630737575,630976938,631338366,634567980,635172621,635470131,636420717,636735376,638911217,640964740,643494983,644041705,650734408,651561500,652471013,656335212,657496902,657780036,657800319,661009608,661943410,663724973,665936391,665955867,666413759,666896952,668306278,668425104,671660080,672298631,675720848,675850467,676337119,676791485,678914881,682193154,684884375,687086291,687289044,688326654,688805517,688906840,689774052,693500433,694439783,695717378,696096390,697576315,699119677,700084838,700677712,701493809,701694566,701937397,703007627,704344737,707087284,708202625,708831405,708871437,709557730,709681509,711350997,714002453,714018685,714187041,714918313,716475606,717176954,717214219,719324100,719635705,721171279,721405376,722256336,724578781,726515524,727130958,727870552,728928708,730833659,731745520,732479026,733739169,734576801,737318078,743966639,744020403,746476494,746614338,749108696,749455331,751257857,752093345,753008955,753286896,753471644,755407473,756733629,756980419,757217074,758087455,758655449,758709389,758889848,762624660,763157678,765463195,765619991,766603386,767877533,768439551,769160809,770431082,770651798,773508942,776650514,777224043,777421126,777977615,778229427,779118106,781261110,783273202,783622451,786756121,788108772,788926126,790502325,797712880,799756012,800473552,801114800,802912146,802922943,803738996,805203848,805321445,805381056,807988674,809676893,815846526,818504672,821874013,822896361,823649914,823927420,824165179,824573829,825274383,825947487,826814013,827148472,828552957,832755181,832937699,834191669,834962652,836644759,837225252,838763304,840232208,845509639,851587645,852300110,853343156,854702560,856185391,858824325,858963867,859452283,861127311,861412347,862665826,862678758,864380345,865461085,871386868,873767170,874492133,874787104,876011808,876654909,877071302,877319588,878536993,880677047,881239887,881598639,881888628,883567019,884438668,884797082,885773728,887011459,889648065,891503932,893335464,893910176,895950263,896600877,898352618,899621329,901061628,901166144,901350385,901697713,902342948,904413299,904516917,905461196,907110699,907748371,910248594,910422311,910882806,912559732,913002234,918028097,919597742,920099850,921998778,922261728,923200623,924381388,924629636,926272617,929262340,932435837,934670279,935623266,936045126,938443014,939135676,941168116,941586662,943504394,945088728,947189986,949316674,951129193,953403358,953561021,955897323,958011752,959294514,959632657,963971474,964840067,966401177,966609676,970719919,971874537,972584348,972916703,975674317,975679210,977669038,979496732,980618570,980817727,983110557,984120047,984676004,985464753,986333295,987204952,987965771,989837914,990048311,990758846,991515606,992367201,993349328,993666396,995552914,996489140,998275927,999136057,999312751]
A= [1,2,3,4,5,6,7,8] # 01234567
so = Solution()
print(so.lenLongestFibSubseq(B))