Statistics

Problem Statement for "TriangularSubsequence"

Problem Statement

Three numbers x, y and z are said to satisfy the triangle inequality if x + y > z, x + z > y, and y + z > x.

The sequence of integers b[0], b[1], ..., b[n-1] is said to be triangular if b[i], b[j] and b[k] satisfy the triangle inequality for all distinct values of i, j and k.

You are given an integer sequence as a int[] a. Return the length of the longest subsequence of a that is triangular. A subsequence of a sequence is obtained by removing zero or more elements from the sequence.

Definition

Class:
TriangularSubsequence
Method:
longest
Parameters:
int[]
Returns:
int
Method signature:
int longest(int[] a)
(be sure your method is public)

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will be between 1 and 10^9, inclusive.

Examples

  1. {2,3,4,1,3,4,5}

    Returns: 5

    The subsequence {2,3,4,3,4} is the longest triangular subsequence.

  2. {1,2,3}

    Returns: 2

    Note that a sequence of length 2 is always triangular.

  3. {1,1,1,1,1,1,1,1}

    Returns: 8

    The whole sequence is triangular.

  4. {1,1,1,1000000000,1000000000,1000000000}

    Returns: 4

  5. {1,2,3,4,5,6,7,8,9,10}

    Returns: 6

  6. {1}

    Returns: 1

  7. {1,1,1,1,1,1,1,1,1,1}

    Returns: 10

  8. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 20

  9. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 30

  10. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 40

  11. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 50

  12. {1,2,3,4,5,6,7,8,9,10}

    Returns: 6

  13. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

    Returns: 11

  14. {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}

    Returns: 16

  15. {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}

    Returns: 21

  16. {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,42,43,44,45,46,47,48,49,50}

    Returns: 26

  17. {10,9,8,7,6,5,4,3,2,1}

    Returns: 6

  18. {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: 11

  19. {30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: 16

  20. {40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: 21

  21. {50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: 26

  22. {4}

    Returns: 1

  23. {21,28,68,32,17,38,43,9,48,8,85,6,30,92,37,78,33,70,85,72,31,17,33,47,25,83,28,49,15,88,29,78,98,50,89,83,3,15,15,51,3,60,1,78}

    Returns: 19

  24. {78,71,56,21,69,60,96,65,100,25,68,30,9,78,50,89,51,58,96,69,34,1,71,99,78,75,20,15,92,79,59,87,69}

    Returns: 25

  25. {10,63,29,88,17,28,55,97,18,16,27,18,58,50,29}

    Returns: 8

  26. {61,74,75,9,8,6,11,80}

    Returns: 4

  27. {39,62,44,75,50,35,82,82,15,10,7,7,20,68,23,58,26,37,84,32,32,66,70,91,32,48,30,77,75,56,73,42,55,60,89,67,12,48,41,12,6}

    Returns: 22

  28. {68,9,93,84,69,93,28,71,74,50,67,16,24,95,37,13,99,31,6,11,87,56,70,11,67,2,31,91}

    Returns: 16

  29. {33,45,91,35,36,49,8,86,77,19,93,50,13,90,41,21,81,59,11,63,93,55,33,45,23,19,70}

    Returns: 14

  30. {63,70,55,10,75,15,24,89,72,44,99,16,4,19,1,38,40,37,9,46,51,47,68,82,57,26,38,59,88,61,26,70,56,88,37,37,63,79,46,21,70,84,76,91,19,78,27,30,71,46}

    Returns: 28

  31. {19,2,23,90,33,87,77,97,28,40,84,3,25,6,51,43,1,16,71,32,40,55,27,16,30,8,71,34,79,66,57,90,3,26,89,69,4,16,16,42,42,15,1,53,77,58,24,87,7}

    Returns: 19

  32. {8,37,67,21,81,53,42,4,100,17,5,6,11,81,96,12,22,77,99,50,4,60,81,93,52}

    Returns: 13

  33. {100,77,72,90,100,74,79,2,37,32,8,79,27,86,92,5,90,93,49,69,38,43,75,70,35,63,51,97,11,100,3,62,36,52}

    Returns: 21

  34. {82,64,96,50,49,100,24,20,44,69,76,4,62,81,47,17,64,8,97,79,88,44,1,23,58,89,6,48,94,87,86,73,99}

    Returns: 20

  35. {16,67,83,19,2,82,57,47,44,15,80}

    Returns: 7

  36. {10,60,80,22,48,41,51,71,79,32,4,61,30,6,47,22,9,66,86,35,31,48,92,73,42,9,81,26,4,35,89,87,44,26,43,37,66,43,64,76,82,46,54,62}

    Returns: 24

  37. {25,41,73,66,18,97,4,33,90,47,52,88,68,42,59,15}

    Returns: 9

  38. {48,16,32,62,82,49,14,47,15,34,67,83,86,16,18,75,28,35,25,4,91,69,9,67,2,62,59,78,20,90,82,65,49,79,75,20,38,91,53,88,73,30,60,11,35,36,43,58,92}

    Returns: 28

  39. {74,100,36,10,41,28,93,24,39,9,53,52,54,23,20,42,97,51,58,38,38,79,92,69,58,53,93,23,3,98,50,98,21,83}

    Returns: 19

  40. {44,7,100,39,71}

    Returns: 3

  41. {83,40,66,28,87,19,37,42,9,97,1,19,11,7,64,28,81,12,70,41,49,53,11,94,33,96,28,80,86,43,51,29,73,34,43,44,98,37,59,71,49,18,33,42}

    Returns: 20

  42. {31379940}

    Returns: 1

  43. {202580966,272921268,671654419,318691272,161795466,372238359,425673768,82012160,474794065,70569331,840854435,59724235,293296572,917284709,367906479,774664898,327925536,697674975,844170970,717982858,306641305,162625852,329496454,466020460,246653648,825676417,279029484,481766318,149184935,874335014,287294203,772753269,976459890,492527988,887936004,827276628,20296893,141056224,143504240,500807768,21675853,592934506,9649000,774478005}

    Returns: 19

  44. {770488684,708106956,557507795,206030096,681085653,592851256,955456249,644055563,998371149,243780497,676165955,295695031,85890351,772321749,495278118,881683812,509966300,573322641,953193002,684833787,338711131,7607521,705350700,988937213,774045116,749572665,197707204,143647095,913598517,784195556,589280793,864709121,689371255}

    Returns: 25

  45. {93643729,628920156,280025393,877184656,161234274,273188303,543685424,960792240,174364010,157069521,268121382,177457313,576795479,498155810,285189756}

    Returns: 8

  46. {609765128,739689961,746407222,80351585,76326574,59781855,106532185,795514785}

    Returns: 4

  47. {381601346,612029137,436832971,740826936,493922685,341290821,818877285,817032662,141395520,93493216,67166288,60292519,193917456,672958324,227479924,570355835,254483172,365899784,837087545,314575237,314885110,656426281,692265006,902992107,318640716,478677783,296475814,766742337,740521251,551969579,723591343,411657406,542057162,595819140,880525111,668935770,112395015,471730781,403656123,114759553,53880993}

    Returns: 22

  48. {673416269,80731570,921745951,838704499,681416791,927007640,277267040,700880831,734488810,499999230,663780891,158221775,230012918,946521402,364923358,126709338,986912825,306261073,54470828,101934447,866688080,554440594,697158096,100686298,668860844,16551630,309847791,904299532}

    Returns: 16

  49. {327034366,442426379,900634207,347179716,353777013,487801718,71563597,850801084,760310637,180377179,922844795,493562478,127574292,892377332,403247134,207542973,807125472,587400190,109813411,623220236,927670869,540571018,326128936,448315740,226792453,184672704,690473387}

    Returns: 14

  50. {629743853,691627693,540730473,97211106,747192059,148706484,232930422,880326745,713779434,438837687,980300265,154456046,39381037,184394644,9696951,378834914,394932260,363833614,82298257,453834662,504701779,460558518,675426524,817580664,566884811,253387249,372380196,582610063,874391696,607994539,257148178,696943558,557706774,878706400,360882004,363946235,621692594,780021112,457000814,205352475,698214419,837231787,751804153,901829917,186460050,775525489,267467571,295457485,702829969,456933916}

    Returns: 28

  51. {188492479,12272783,224510647,899110202,322801725,862940985,763109951,966640374,274331793,396042032,836142158,20803446,246993273,52759731,507680592,422737521,334112,150120933,709295068,312469408,395377022,547682553,260986949,151089909,292995941,76913888,705600770,330311930,789206560,655149256,566087418,896286391,21745915,255985946,884993881,684550967,32316037,158002476,155554554,412986620,418866672,143672174,3759114,529656963,762292049,570347057,230771948,862405424,61916729}

    Returns: 19

  52. {75078155,367085226,664145504,205909423,803731101,521297182,418652359,39233761,992076540,160510300,46483505,58896956,101328299,803440199,954449462,115113728,213370524,763560343,980181218,497357372,32161488,593621081,802225441,922335832,511113962}

    Returns: 13

  53. {999553754,769038090,715827149,894119111,994861079,732725863,781545180,16722292,366028038,319745614,74717174,783690619,260122415,855035881,918033855,48467954,894314687,924204906,488315739,689053365,378082613,422053591,746627882,696074854,341079884,629418756,509996182,968870907,101043843,990211716,24100257,616454841,356117255,510527165}

    Returns: 21

  54. {810236980,635959154,951697376,498495947,485379629,996019741,239166714,198823097,437659870,689354349,759061458,32178768,612715168,800351474,464329941,168333918,634546787,74749859,962327995,787378259,870156023,430319653,5724716,221749066,577188245,882582620,58603538,474236553,931459749,869946419,859633618,721340802,981242430}

    Returns: 20

  55. {154186536,661355260,825181261,189740730,17273306,816551799,560719582,468921404,439176703,148842336,799907213}

    Returns: 7

  56. {95653896,598292016,799466365,217180694,474584401,403858959,501990374,703833141,780938338,315735570,35150244,604727514,291940009,58666406,465784000,219630114,84301786,655617614,855743860,342909446,305403304,471172925,916376211,723436122,410290978,84031212,808509405,252021823,36372828,347980612,884824363,860772329,437683610,250724212,421482996,368729608,650595270,429932288,635889429,758177967,812847707,455896123,537459052,615989268}

    Returns: 24

  57. {240158369,408270368,724382206,655601003,179494989,960474667,35470648,323682640,894623745,467338502,513976035,877570316,673014263,414793986,582478847,144766042}

    Returns: 9

  58. {470371892,153584133,313050916,613789686,816392579,483376095,135258064,465085551,144289713,330536746,662365909,821796155,856941818,155503623,176786742,747105998,275886627,344041563,247725607,38944606,900293250,689603543,80484506,664007525,14567159,618855585,581586904,770878884,191462974,894740719,811597558,641630509,487580074,781457010,747512651,191272617,378116012,905724647,526595243,874431051,727752749,298717097,593531030,108626096,344550690,353031322,422779424,573527848,913725549}

    Returns: 28

  59. {737994933,995563146,358183008,95225124,400393863,277249071,922686204,236194891,387941330,80628003,528531018,513880681,537233586,224179240,195604181,415167327,969950651,502582185,578699195,371004755,375754267,788706094,914965059,681151637,573506157,527201375,929362817,228958108,22681600,979067472,495004909,970562539,206853316,826572288}

    Returns: 19

  60. {432877382,61120671,997898187,384444661,704739069}

    Returns: 3

  61. {820889550,394137765,655596975,275165336,865276897,181724487,366116452,412371752,82752571,968313024,5070912,187007599,104272984,62738169,636897982,272579375,803962423,118580348,694294721,406546979,488993426,521067479,100226893,937870094,324818712,950734642,273727311,793499891,855129677,420716554,503858236,285691037,725916455,334547865,426212844,432009021,973004536,361346265,586330752,709907790,482442953,175253399,324402610,417752698}

    Returns: 20

  62. {1,31379940,861048468,202580966,272921268,671654419,318691272,161795466,372238359,425673768,82012160,474794065,70569331,840854435,59724235,293296572,917284709,367906479,774664898,327925536,697674975,844170970,717982858,306641305,162625852,329496454,466020460,246653648,825676417,279029484,481766318,149184935,874335014,287294203,772753269,976459890,492527988,887936004,827276628,20296893,141056224,143504240,500807768,21675853,592934506,9649000,774478005,650657643,770488684,708106956}

    Returns: 23

  63. {557507795,206030096,681085653,592851256,955456249,644055563,998371149,243780497,676165955,295695031,85890351,772321749,495278118,881683812,509966300,573322641,953193002,684833787,338711131,7607521,705350700,988937213,774045116,749572665,197707204,143647095,913598517,784195556,589280793,864709121,689371255,287833227,93643729,628920156,280025393,877184656,161234274,273188303,543685424,960792240,174364010,157069521,268121382,177457313,576795479,498155810,285189756,155944744,609765128,739689961}

    Returns: 30

  64. {746407222,80351585,76326574,59781855,106532185,795514785,805889180,381601346,612029137,436832971,740826936,493922685,341290821,818877285,817032662,141395520,93493216,67166288,60292519,193917456,672958324,227479924,570355835,254483172,365899784,837087545,314575237,314885110,656426281,692265006,902992107,318640716,478677783,296475814,766742337,740521251,551969579,723591343,411657406,542057162,595819140,880525111,668935770,112395015,471730781,403656123,114759553,53880993,548613146,673416269}

    Returns: 27

  65. {80731570,921745951,838704499,681416791,927007640,277267040,700880831,734488810,499999230,663780891,158221775,230012918,946521402,364923358,126709338,986912825,306261073,54470828,101934447,866688080,554440594,697158096,100686298,668860844,16551630,309847791,904299532,535211733,327034366,442426379,900634207,347179716,353777013,487801718,71563597,850801084,760310637,180377179,922844795,493562478,127574292,892377332,403247134,207542973,807125472,587400190,109813411,623220236,927670869,540571018}

    Returns: 27

  66. {326128936,448315740,226792453,184672704,690473387,996054038,629743853,691627693,540730473,97211106,747192059,148706484,232930422,880326745,713779434,438837687,980300265,154456046,39381037,184394644,9696951,378834914,394932260,363833614,82298257,453834662,504701779,460558518,675426524,817580664,566884811,253387249,372380196,582610063,874391696,607994539,257148178,696943558,557706774,878706400,360882004,363946235,621692594,780021112,457000814,205352475,698214419,837231787,751804153,901829917}

    Returns: 27

  67. {186460050,775525489,267467571,295457485,702829969,456933916,964296044,188492479,12272783,224510647,899110202,322801725,862940985,763109951,966640374,274331793,396042032,836142158,20803446,246993273,52759731,507680592,422737521,334112,150120933,709295068,312469408,395377022,547682553,260986949,151089909,292995941,76913888,705600770,330311930,789206560,655149256,566087418,896286391,21745915,255985946,884993881,684550967,32316037,158002476,155554554,412986620,418866672,143672174,3759114}

    Returns: 18

  68. {529656963,762292049,570347057,230771948,862405424,61916729,485187035,75078155,367085226,664145504,205909423,803731101,521297182,418652359,39233761,992076540,160510300,46483505,58896956,101328299,803440199,954449462,115113728,213370524,763560343,980181218,497357372,32161488,593621081,802225441,922335832,511113962,660051504,999553754,769038090,715827149,894119111,994861079,732725863,781545180,16722292,366028038,319745614,74717174,783690619,260122415,855035881,918033855,48467954,894314687}

    Returns: 29

  69. {924204906,488315739,689053365,378082613,422053591,746627882,696074854,341079884,629418756,509996182,968870907,101043843,990211716,24100257,616454841,356117255,510527165,646317874,810236980,635959154,951697376,498495947,485379629,996019741,239166714,198823097,437659870,689354349,759061458,32178768,612715168,800351474,464329941,168333918,634546787,74749859,962327995,787378259,870156023,430319653,5724716,221749066,577188245,882582620,58603538,474236553,931459749,869946419,859633618,721340802}

    Returns: 30

  70. {981242430,212627946,154186536,661355260,825181261,189740730,17273306,816551799,560719582,468921404,439176703,148842336,799907213,872870232,95653896,598292016,799466365,217180694,474584401,403858959,501990374,703833141,780938338,315735570,35150244,604727514,291940009,58666406,465784000,219630114,84301786,655617614,855743860,342909446,305403304,471172925,916376211,723436122,410290978,84031212,808509405,252021823,36372828,347980612,884824363,860772329,437683610,250724212,421482996,368729608}

    Returns: 23

  71. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 50

  72. {1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,999999990,999999989,999999988,999999987,999999986,999999985,999999984,999999983,999999982,999999981,999999980,999999979,999999978,999999977,999999976,999999975,999999974,999999973,999999972,999999971,999999970,999999969,999999968,999999967,999999966,999999965,999999964,999999963,999999962,999999961,999999960,999999959,999999958,999999957,999999956,999999955,999999954,999999953,999999952,999999951}

    Returns: 50

  73. {1000000000}

    Returns: 1

  74. {1,1}

    Returns: 2

  75. {546725227, 674932909, 774111577, 462107874, 466835066, 538309710, 679769881, 907905277, 416731052, 407991282, 446124218, 697456899, 945588267, 795594539, 948141230, 713593048, 504173676, 904173358, 502895862, 877808152, 356513839, 900405273, 723150204, 553378414, 826807792, 955614624, 688308917, 509405629, 808985009, 740889040, 723015114, 355710235, 415821948, 949643046, 920334465, 985173370, 487952756, 600104345, 695595001, 554683808, 658095627, 791719220, 704657062, 406200248, 587313758, 455314647, 769793296, 544003789, 359488004, 725205514 }

    Returns: 39

  76. {1, 2 }

    Returns: 2

  77. {10, 11, 12, 13, 14, 15, 16, 17, 1000, 1000, 1500 }

    Returns: 8

  78. {3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 7 }

    Returns: 12

  79. {3, 10, 100, 300, 2, 1 }

    Returns: 2

  80. {2, 6, 4, 5, 7, 8, 4, 6, 8, 90, 5, 3, 456, 5, 6, 6, 4, 5, 67, 6, 56, 4, 4, 6, 7, 8, 9, 2, 3, 4, 5, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 4, 345, 23, 12, 13, 14, 15 }

    Returns: 28

  81. {1, 2, 3, 4, 6, 8, 10, 12, 14, 16, 18 }

    Returns: 5

  82. {2, 2, 3, 3, 3, 7 }

    Returns: 5

  83. {1, 1, 100000, 100000, 100000, 100000, 100000, 100000000, 100000000 }

    Returns: 6

  84. {1, 2, 34, 4, 3, 3, 6, 5, 8, 2, 4 }

    Returns: 5

  85. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: 50

  86. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000000000 }

    Returns: 49

  87. {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 60000000, 100000000 }

    Returns: 3

  88. {3, 3, 3, 6, 2, 7, 1, 15, 54, 21, 41, 18, 28, 24, 2, 4, 15, 4, 85, 4, 88, 574, 5854, 5452, 854, 584, 584, 587, 21, 45, 8452, 54, 842, 45, 424, 554, 24, 25, 412, 54, 245, 4254, 254, 254, 24254, 2, 542, 452, 4, 5 }

    Returns: 10

  89. {2, 2, 3, 100 }

    Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: