Problem Statement
The following operation can be repeatedly used to generate energy:
- Choose a star x other than the very first star and the very last star.
- The x-th star disappears.
- This generates weight[x-1] * weight[x+1] units of energy.
- We decrease n and relabel the stars 0 through n-1 from the left to the right.
Your task is to use the device to generate as many units of energy as possible. Return the largest possible total amount of generated energy.
Definition
- Class:
- CasketOfStarEasy
- Method:
- maxEnergy
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int maxEnergy(int[] weight)
- (be sure your method is public)
Constraints
- weight will contain between 3 and 10 elements, inclusive.
- Each element in weight will be between 1 and 1,000, inclusive.
Examples
{1,2,3,4}
Returns: 12
We have only 2 choices: Make the "2" disappear first, and "3" next. The total energy is 1*3 + 1*4 = 7. Make the "3" disappear first, and "2" next. The total energy is 2*4 + 1*4 = 12. So the answer is 12.
{100,2,1,3,100}
Returns: 10400
We proceed as follows: {100,2,1,3,100} => {100,1,3,100} => {100,3,100} => {100,100} The total energy is 100*1 + 100*3 + 100*100 = 10400.
{2,2,7,6,90,5,9}
Returns: 1818
{477,744,474,777,447,747,777,474}
Returns: 2937051
{1,1,1,1,1,1,1,1,1,1}
Returns: 8
{213,220,224,224,197}
Returns: 138953
{784,783,785,785,784,783,785,785,783}
Returns: 4308867
{526,530,662,627,472,601,626,603,634}
Returns: 2689691
{422,792,433}
Returns: 182726
{546,529,545}
Returns: 297570
{481,652,652}
Returns: 313612
{748,704,728}
Returns: 544544
{864,638,752,820,721,697,830,726,447,664}
Returns: 5037382
{531,342,276,421,349,279,392,183}
Returns: 1008900
{115,88,90,107}
Returns: 22655
{375,402,431}
Returns: 161625
{486,555,593,564,589,576,582,563,635,502}
Returns: 2749047
{271,315,235,313,359,341}
Returns: 411506
{615,555,564,636,590,549}
Returns: 1444605
{670,874,622,897,928,544}
Returns: 2581290
{714,761,694,754,769,807,727}
Returns: 2891675
{175,191,133,279,134,280}
Returns: 233889
{662,597,613,622,669}
Returns: 1260448
{810,743,746}
Returns: 604260
{713,518,558,655,494,703,565,460,670}
Returns: 3153843
{849,869,768,809,903,859}
Returns: 2983666
{334,271,372}
Returns: 124248
{153,213,297,337,117,329}
Returns: 329000
{496,474,343,366,333,362,469,379,530}
Returns: 1506790
{293,801,418,330,883}
Returns: 1335096
{963,893,836,970,917,909,929,839,896}
Returns: 6173039
{335,339,580,428}
Returns: 337680
{799,320,437,941,323,408,252,507,628}
Returns: 3291889
{724,728,420,446,794,545,782}
Returns: 2673444
{799,800,842,784}
Returns: 1299174
{582,359,398,382,602,550}
Returns: 1141696
{703,860,888,761,744}
Returns: 1823544
{116,134,221,229,210,108,200,235}
Returns: 255850
{459,386,283}
Returns: 129897
{695,563,523,586,659,748,488,728,564}
Returns: 3213000
{531,695,588,670}
Returns: 821420
{246,621,649,307,831,430,705,285,579}
Returns: 3032562
{203,341,270,175,628,416,171,368,232,509}
Returns: 1551760
{492,238,217}
Returns: 106764
{566,569,598,635,639,592,617}
Returns: 1856005
{661,357,192,503,330,745,770,301,702}
Returns: 2906786
{321,256,208,62,245,168}
Returns: 250301
{265,267,327}
Returns: 86655
{630,719,679}
Returns: 427770
{491,592,475,442,500}
Returns: 803164
{432,446,406,474}
Returns: 416172
{35,226,218,191,80,131}
Returns: 102378
{291,220,135,186,197,121,114,151,252}
Returns: 338031
{349,393,250,476,325,490,460,199,577,230}
Returns: 1751514
{920,945,912,915,943,932,935}
Returns: 4381290
{114,123,119,115,120,130,130,122}
Returns: 91314
{340,342,726,438,645,302,518}
Returns: 1601408
{392,178,617,119,518,281,630,401,747,218}
Returns: 2586309
{219,212,213,290,311,272,248,313}
Returns: 474821
{215,261,203,252,357,430,246,230}
Returns: 548680
{743,775,636,741,590,591,744}
Returns: 2693931
{105,403,293,335}
Returns: 170180
{512,559,865,384,619,655}
Returns: 1880250
{719,214,204,508}
Returns: 511928
{566,529,385,563,503,393,529,403}
Returns: 1707911
{410,526,377,536,280,511,510,497,252}
Returns: 1665964
{184,712,785,634,375,799,786}
Returns: 2455047
{634,647,615,623,642,646}
Returns: 1645981
{619,663,650,646,672}
Returns: 1298304
{710,834,828,757,742,829}
Returns: 2593941
{292,242,342,236,392,442,176,381,300,357}
Returns: 1087713
{793,872,782,791,782}
Returns: 1991782
{336,315,321,313}
Returns: 213024
{817,732,755}
Returns: 616835
{146,140,87,363}
Returns: 103818
{874,872,858}
Returns: 749892
{237,392,103,250,473,121,128,82,319,453}
Returns: 1034885
{826,814,598,684,532,775,517,511,666,728}
Returns: 4435579
{283,390,247,265,163,101}
Returns: 253057
{779,744,778,716,715}
Returns: 1720811
{598,618,488,800,518,798,805,722,580}
Returns: 3643640
{451,247,211,239,324,228}
Returns: 451902
{74,153,405,168,223,55,146}
Returns: 222777
{650,648,634,630,629,642,648,652,653,634}
Returns: 3338193
{607,610,613}
Returns: 372091
{100, 3, 1, 2, 100 }
Returns: 10400
{2, 3, 2, 1, 2 }
Returns: 14
{3, 8, 21, 8, 3 }
Returns: 135
{100, 4, 2, 1, 3, 100 }
Returns: 10700
{1, 3, 5, 2, 1, 2, 5 }
Returns: 60
{1, 2, 3, 4 }
Returns: 12
{1, 2, 7, 4, 1, 2, 3 }
Returns: 53
{1, 1, 10, 90, 10, 1 }
Returns: 271
{3, 10, 25, 10, 3 }
Returns: 159
{8, 16, 8, 4, 4 }
Returns: 160
{10, 21, 6, 9, 1, 8, 7, 3, 4, 1 }
Returns: 773
{8, 1, 8, 64, 32, 1, 2 }
Returns: 912
{5, 6, 7, 8, 9, 8, 7, 6, 5 }
Returns: 349
{4, 1, 5, 8, 5, 1, 4 }
Returns: 120
{999, 997, 998, 995, 996, 1, 2, 3, 4, 1000 }
Returns: 4993966
{10, 2, 1, 1, 10 }
Returns: 130
{50, 1000, 50, 1, 50 }
Returns: 55000
{10, 100, 3, 200, 9 }
Returns: 22090
{400, 1000, 60, 2, 60, 1000 }
Returns: 1463600
{363, 28, 691, 60, 764, 927, 541, 427, 173, 737 }
Returns: 3592727
{3, 5, 7, 4, 8, 3, 2, 1, 8, 3 }
Returns: 289
{1, 2, 3, 2, 1, 2 }
Returns: 16
{1000, 1, 1000, 2, 1000, 4, 1000, 500, 2, 2 }
Returns: 5504000
{897, 802, 765, 992, 1, 521, 220, 380, 729, 969 }
Returns: 5351049
{10, 100, 10, 1, 10 }
Returns: 1200
{2, 5, 3, 1, 1, 4 }
Returns: 44
{1, 25, 100, 30, 2, 3, 4, 1, 100, 1 }
Returns: 16501
{1000, 223, 345, 460, 521, 633, 784, 385, 249, 1000 }
Returns: 4912000
{100, 20, 5, 1, 100 }
Returns: 12500
{100, 5, 1, 1, 100 }
Returns: 10600
{60, 49, 80, 23, 54, 90, 12, 95, 26, 59 }
Returns: 47315
{1, 100, 800, 100, 1, 1, 800, 1, 1 }
Returns: 802401
{7, 3, 1, 2, 7 }
Returns: 77
{1, 1, 1, 1, 1, 1, 2, 3, 2, 1 }
Returns: 22
{80, 40, 2, 50, 88, 50 }
Returns: 17040
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }
Returns: 32
{100, 200, 500, 894, 451, 984, 102, 1, 874, 874 }
Returns: 4169432
{20, 25, 20, 15, 19 }
Returns: 1235
{9, 3, 5, 9, 10 }
Returns: 216
{50, 90, 1, 8, 1, 1, 300 }
Returns: 45420
{100, 1, 3, 100, 3, 1, 3, 1, 100 }
Returns: 31000
{1, 1, 2, 1, 1, 1, 2, 5, 3 }
Returns: 38
{100, 2, 100, 2 }
Returns: 10200
{1, 1, 4, 8, 4, 1, 1, 8 }
Returns: 152
{477, 744, 474, 777, 447, 747, 777, 474 }
Returns: 2937051
{2, 4, 7, 4, 2 }
Returns: 32
{1, 7, 8, 6 }
Returns: 48
{3, 10, 4, 1, 1, 8 }
Returns: 144
{1, 90, 1000, 3, 1, 5, 1000, 11, 90, 2 }
Returns: 1194282
{100, 3, 2, 1, 100 }
Returns: 10500
{100, 49, 1, 2, 100 }
Returns: 15000
{1, 3, 11, 4, 1 }
Returns: 23
{1, 10, 100, 11, 1, 1 }
Returns: 301
{100, 3, 100, 1000, 101 }
Returns: 120100
{2, 4, 3, 1, 1 }
Returns: 11
{88, 40, 2, 50, 88, 50 }
Returns: 18544
{3, 2, 1, 8, 4, 7, 9, 3, 9, 9 }
Returns: 429
{872, 1, 437, 101, 1, 605, 721, 997, 17, 1 }
Returns: 2747906
{69, 38, 29, 46, 72 }
Returns: 10143
{6, 1, 5, 9, 8 }
Returns: 132
{712, 546, 712, 364, 712, 678, 453, 999, 804, 243 }
Returns: 4609048
{3, 1, 4, 10, 3 }
Returns: 51
{7, 50, 8, 1, 5 }
Returns: 335