Statistics

Problem Statement for "BlockTower"

Problem Statement

Josh loves playing with blocks. Currently, he has N blocks, labeled 0 through N-1. The heights of all blocks are positive integers. More precisely, for each i, the height of block i is blockHeights[i]. Josh is interested in making the tallest block tower possible. He likes all his towers to follow three simple rules:
  1. The blocks must be stacked in a single column, one atop another. The height of the tower is simply the sum of heights of all its blocks.
  2. The labels of blocks used in the tower must increase from the bottom to the top. In other words, whenever Josh places box x on top of box y, we have x > y.
  3. Josh will never place a box of an even height on top of a box of an odd height.
You are given the int[] blockHeights. Return the height of the tallest possible block tower Josh can build.

Definition

Class:
BlockTower
Method:
getTallest
Parameters:
int[]
Returns:
int
Method signature:
int getTallest(int[] blockHeights)
(be sure your method is public)

Constraints

  • blockHeights will contain between 1 and 50 elements, inclusive.
  • Each element of blockHeights will be between 1 and 50, inclusive.

Examples

  1. {4,7}

    Returns: 11

    The optimal tower contains both blocks. Block 0 is on the bottom of the tower.

  2. {7,4}

    Returns: 7

    This time the optimal tower contains just block 0. Josh cannot put block 1 on top of it, because 4 is even and 7 is odd.

  3. {7}

    Returns: 7

  4. {4}

    Returns: 4

  5. {48,1,50,1,50,1,48}

    Returns: 196

    Note that in a valid tower the labels of the blocks have to increase from bottom to top. Their heights do not have to. In this case the optimal tower consists of blocks 0, 2, 4, and 6, in this order. Its total height is 48 + 50 + 50 + 48 = 196.

  6. {49,2,49,2,49}

    Returns: 147

  7. {44,3,44,3,44,47,2,47,2,47,2}

    Returns: 273

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

    Returns: 11

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

    Returns: 30

  10. {2,3,4}

    Returns: 6

  11. {1}

    Returns: 1

  12. {50}

    Returns: 50

  13. {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: 675

  14. {50,1,50,1,50,1,50,1,50,1,50}

    Returns: 300

  15. {50,1,50,1,50,1,49,2,49,2,49,2,49,2}

    Returns: 347

  16. {24, 20, 3, 9, 20, 12, 27, 16, 30, 29, 43, 8, 27, 38, 42, 1, 25, 34, 8, 23, 27, 22, 47, 39, 41, 41, 44, 12, 24, 36, 19, 37, 46, 9, 27, 22, 34, 12, 46, 41, 36, 42, 11, 45, 20, 2, 27, 46, 50, 19}

    Returns: 765

  17. {30, 14, 2, 49, 41, 50, 10, 14, 29, 34, 9, 11, 12, 16, 46, 20, 46, 48, 38, 43, 4, 39, 43, 11, 46, 10, 43, 20, 45, 12, 29, 18, 47, 41, 14, 10, 35, 10, 35, 43, 21, 22, 48, 40, 22, 3, 47, 47, 34, 13}

    Returns: 965

  18. {23, 34, 18, 1, 28, 28, 33, 35, 16, 11, 16, 15, 1, 30, 11, 28, 16, 28, 3, 10, 28, 42, 47, 44, 18, 43, 10, 14, 25, 45, 17, 11, 40, 45, 17, 25, 10, 35, 47, 17, 37, 18, 25, 14, 49, 23, 39, 3, 45, 47}

    Returns: 979

  19. {44, 29, 22, 33, 20, 2, 5, 10, 39, 43, 3, 43, 27, 27, 47, 45, 44, 22, 28, 40, 12, 24, 30, 48, 34, 35, 34, 22, 14, 4, 33, 20, 15, 50, 15, 27, 45, 6, 34, 18, 19, 17, 24, 19, 28, 19, 23, 1, 26, 34}

    Returns: 709

  20. {17, 26, 27, 10, 28, 7, 26, 14, 32, 3, 14, 20, 19, 47, 3, 42, 32, 33, 32, 24, 32, 38, 39, 10, 42, 2, 37, 10, 36, 17, 42, 49, 44, 15, 9, 43, 7, 50, 21, 21, 14, 43, 22, 26, 30, 38, 34, 5, 49, 34}

    Returns: 824

  21. {47, 32, 49, 24, 13, 32, 4, 34, 10, 14, 14, 19, 17, 18, 49, 3, 45, 2, 16, 28, 34, 21, 32, 43, 38, 31, 1, 15, 7, 3, 13, 20, 33, 12, 16, 19, 4, 49, 3, 5, 22, 35, 43, 38, 48, 43, 5, 39, 8, 29}

    Returns: 734

  22. {22, 8, 20, 32, 25, 37, 35, 47, 34, 18, 36, 6, 15, 3, 16, 25, 10, 31, 3, 36, 42, 33, 19, 8, 22, 8, 24, 43, 24, 29, 49, 23, 6, 36, 43, 2, 3, 7, 46, 4, 29, 37, 44, 28, 15, 49, 35, 36, 28, 23}

    Returns: 740

  23. {23, 38, 3, 19, 28, 40, 28, 17, 10, 33, 16, 49, 1, 50, 20, 5, 42, 2, 6, 7, 5, 25, 35, 39, 37, 44, 42, 22, 22, 6, 33, 16, 5, 42, 37, 47, 41, 16, 49, 27, 46, 14, 17, 17, 44, 20, 8, 42, 24, 34}

    Returns: 722

  24. {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

    Returns: 150

  25. {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: 200

  26. {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}

    Returns: 450

  27. {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}

    Returns: 500

  28. {19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19}

    Returns: 950

  29. {49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 10, 10, 27, 34, 4, 35, 38, 40, 22, 21, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

    Returns: 1158

  30. {49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 3, 18, 9, 45, 24, 26, 2, 5, 30, 33, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

    Returns: 1100

  31. {49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 34, 1, 36, 31, 13, 1, 39, 37, 11, 12, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

    Returns: 1113

  32. {49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 47, 35, 15, 6, 6, 22, 17, 24, 11, 48, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

    Returns: 1106

  33. {31, 48}

    Returns: 48

  34. {13, 30, 12, 7}

    Returns: 49

  35. {23, 3, 24, 35, 24}

    Returns: 61

  36. {37, 24, 12, 24, 33, 50, 1, 20, 47, 24, 37, 15, 36, 42, 9, 42, 5, 42, 16, 8, 35, 23, 32}

    Returns: 398

  37. {24, 44, 31, 18, 22, 11, 26, 33, 49, 33, 13, 20, 2, 46, 27, 50, 43, 29, 44, 16, 4, 19, 29, 38}

    Returns: 409

  38. {18, 42, 41, 1, 22, 39, 35, 3, 13, 26, 43, 23, 26, 7, 28, 23, 49, 41, 14, 48, 40, 22, 19, 35, 38, 11, 6, 38, 38, 48, 19, 24, 20, 3, 15, 2}

    Returns: 516

  39. {29, 39, 46, 36, 37, 36, 20, 30, 49, 28, 30, 37, 15, 34, 35, 4, 4, 43, 35, 31, 5, 26, 3, 5, 37, 7, 26, 15, 28, 20, 13, 15, 1, 28, 1, 18, 40}

    Returns: 524

  40. {46, 14, 15, 23, 43, 15, 5, 38, 19, 20, 11, 40, 16, 6, 36, 6, 39, 48, 42, 40, 18, 21, 6, 39, 46, 38, 47, 31, 14, 29, 33, 17, 37, 33, 13, 48, 12, 41}

    Returns: 741

  41. {26, 3, 28, 18, 2, 33, 27, 47, 48, 6, 47, 18, 13, 31, 36, 24, 16, 49, 9, 21, 39, 11, 47, 38, 32, 22, 45, 14, 18, 34, 2, 33, 12, 35, 11, 47, 44, 42, 37}

    Returns: 656

  42. {2, 34, 47, 22, 45, 45, 44, 20, 24, 14, 19, 25, 41, 19, 32, 23, 47, 46, 13, 22, 24, 36, 35, 15, 15, 43, 8, 40, 39, 7, 26, 17, 49, 9, 4, 15, 22, 48, 11, 5, 37, 43, 31, 41}

    Returns: 772

  43. {16, 38, 38, 23, 37, 28, 22, 39, 26, 2, 8, 45, 2, 30, 48, 44, 25, 2, 33, 49, 22, 6, 6, 10, 35, 19, 11, 15, 2, 41, 14, 46, 24, 33, 44, 41, 38, 18, 43, 49, 36, 7, 28, 31, 15, 12, 18, 40, 33, 17}

    Returns: 799

  44. {1,49,1}

    Returns: 51

  45. {1,48,1}

    Returns: 49

  46. {2,47,2}

    Returns: 49

  47. {3,30,3}

    Returns: 33

  48. {1,2,1,2,1,2,2,2,2,2,1,1,1,1,1}

    Returns: 19

  49. {2, 24, 20, 10, 22, 18, 39, 18, 46, 27}

    Returns: 187

  50. {25, 33, 18, 13, 24, 41, 4, 44, 42, 49}

    Returns: 181

  51. {42, 1, 1, 9, 48, 18, 9, 21, 4, 34}

    Returns: 146

  52. {16, 29, 50, 4, 34, 27, 10, 47, 44, 21}

    Returns: 199

  53. {36, 25, 23, 19, 49, 9, 23, 46, 32, 39}

    Returns: 223

  54. {7, 10, 30, 21, 23, 26, 1, 42, 5, 24}

    Returns: 132

  55. {7, 37, 27, 10, 50, 19, 33, 22, 26, 14}

    Returns: 123

  56. {8, 16, 9, 8, 32, 9, 37, 9, 41, 37}

    Returns: 197

  57. {43, 49, 46, 11, 5, 20, 20, 35, 21, 31}

    Returns: 195

  58. {44, 50, 22, 29, 41, 14, 34, 24, 22, 36}

    Returns: 246

  59. {44, 16, 39, 4, 42, 11, 18, 24, 26, 13}

    Returns: 187

  60. {13, 43, 34, 4, 49, 27, 5, 12, 12, 25}

    Returns: 162

  61. {5, 1, 15, 17, 17, 12, 39, 31, 37, 43}

    Returns: 205

  62. {28, 19, 40, 33, 13, 28, 4, 37, 15, 17}

    Returns: 183

  63. {19, 32, 21, 36, 22, 50, 30, 36, 29, 5}

    Returns: 240

  64. {45, 7, 8, 4, 20, 13, 26, 30, 42, 10}

    Returns: 140

  65. {2, 49, 26, 33, 46, 37, 5, 40, 21, 28}

    Returns: 147

  66. {6, 21, 48, 5, 10, 46, 38, 25, 34, 42}

    Returns: 224

  67. {19, 10, 33, 2, 27, 50, 35, 26, 18, 9}

    Returns: 123

  68. {36, 5, 49, 42}

    Returns: 90

  69. {18, 3, 9, 48, 15, 28, 45, 49, 45}

    Returns: 233

  70. {50, 27, 43, 37, 34, 33}

    Returns: 190

  71. {12, 33, 48, 13, 31}

    Returns: 104

  72. {39, 29, 33, 30, 43, 47}

    Returns: 191

  73. {15, 21, 33, 17, 11, 30, 31, 7, 2}

    Returns: 135

  74. {13, 32, 7}

    Returns: 39

  75. {34, 15, 29, 28, 30, 42, 46, 38, 2, 23, 30}

    Returns: 250

  76. {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: 2500

  77. {23, 48, 47, 38, 12, 20, 37, 31, 33, 19, 41, 42, 49, 24, 34, 15, 45, 43, 40, 46, 37, 10, 19, 49, 11, 24, 48, 7, 20, 21, 36, 31, 49, 15, 47, 7, 38, 44, 5, 20, 3, 33, 48, 19, 28, 21, 49, 43, 12, 25 }

    Returns: 922

  78. {4, 7 }

    Returns: 11

  79. {33, 43, 47, 22, 11, 18, 26, 9, 1, 13, 31, 13, 24, 43, 13, 36, 23, 13, 35, 29, 21, 6, 38, 43, 1, 11, 47, 2, 32, 24, 16, 41, 42, 18, 44, 9, 47, 29, 2, 28, 18, 26, 18, 47, 44, 27, 22, 45, 11, 50 }

    Returns: 736

  80. {10, 7, 7, 7, 10, 7, 7, 7, 20 }

    Returns: 52

  81. {44, 3, 44, 3, 44, 47, 2, 47, 2, 47, 2 }

    Returns: 273

  82. {9, 8, 7, 6, 5 }

    Returns: 21

  83. {1, 3, 4, 5 }

    Returns: 9

  84. {1, 1, 1, 4 }

    Returns: 4

  85. {7, 5, 3, 1 }

    Returns: 16

  86. {4, 7, 20, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2 }

    Returns: 38

  87. {1, 50 }

    Returns: 50

  88. {1, 5, 7, 6, 45, 34, 15, 23, 34, 44, 23, 1, 1, 1, 6, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 28, 30, 32, 44, 49, 48, 48, 45, 40, 40, 40, 40, 32, 30, 30, 16, 14, 14, 14, 12 }

    Returns: 766

  89. {11, 6, 6, 6 }

    Returns: 18

  90. {3, 3, 3, 3, 50 }

    Returns: 50

  91. {1, 2, 1, 5 }

    Returns: 8

  92. {48, 1, 50, 1, 50, 1, 48 }

    Returns: 196

  93. {3, 5, 10 }

    Returns: 10

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

    Returns: 35

  95. {3, 4, 4, 4, 4 }

    Returns: 16

  96. {15, 14, 18, 15, 24, 2, 17, 21, 19, 19, 25, 24, 1 }

    Returns: 160

  97. {2, 47, 2, 48 }

    Returns: 52

  98. {3, 3, 10, 3, 1, 1, 1, 1, 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 }

    Returns: 61

  99. {2, 1, 1, 1, 2 }

    Returns: 5

  100. {3, 3, 3, 14 }

    Returns: 14

  101. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 12 }

    Returns: 12

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

    Returns: 9

  103. {5, 2, 2, 2, 2 }

    Returns: 8

  104. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 33, 50, 34, 45, 50, 50, 34, 23, 34, 23, 45, 23, 5, 3, 2, 6, 34, 23, 21, 22, 4, 34, 34, 34, 44, 33, 45, 45, 34, 45, 34, 42, 30, 34, 34, 45, 50, 45 }

    Returns: 811

  105. {1, 1, 1, 30, 30 }

    Returns: 60

  106. {44, 3, 44, 3, 44, 46, 2, 47, 2, 47, 2, 2 }

    Returns: 274

  107. {2, 1, 1, 33, 40 }

    Returns: 42

  108. {1, 1, 1, 1, 1, 1, 1, 2 }

    Returns: 7

  109. {1, 1, 4 }

    Returns: 4

  110. {2, 3, 4, 5, 6, 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, 40, 45, 46, 47, 48, 49 }

    Returns: 652

  111. {10, 19, 10, 10 }

    Returns: 30

  112. {3, 3, 4 }

    Returns: 6

  113. {15, 14, 18, 15, 24, 2, 17, 21, 19, 19, 25, 24, 1, 29, 35, 18, 21, 20, 24, 29 }

    Returns: 274

  114. {4, 3, 5 }

    Returns: 12

  115. {31, 7, 20 }

    Returns: 38

  116. {4, 6, 13, 14, 21, 23, 22, 24, 15, 18, 23, 27 }

    Returns: 138

  117. {15, 14, 18, 15, 24, 2, 17, 21, 19, 19, 25, 24, 1, 29, 35, 18, 21, 20, 24, 29, 19, 22, 25, 18, 27, 28 }

    Returns: 345

  118. {3, 3, 10, 3, 1, 1, 1, 1, 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 }

    Returns: 68

  119. {7, 7, 4 }

    Returns: 14

  120. {4, 7, 20, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 4, 7, 20, 3, 3, 2, 2, 2, 2 }

    Returns: 70

  121. {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

  122. {27, 23, 26 }

    Returns: 50

  123. {2, 2, 2, 9, 6, 4, 3, 9, 4, 2, 2, 11 }

    Returns: 39

  124. {34, 37, 28, 16, 44, 36, 37, 43, 50, 22, 13, 28, 41, 10, 14, 27, 41, 27, 23, 37, 12, 19, 18, 30, 33, 31, 13, 24, 18, 36, 30, 3, 23, 9, 20, 18, 44, 7, 12, 43, 30, 24, 22, 20, 35, 38, 49, 25, 16 }

    Returns: 752

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: