Problem Statement
Manao is going to cut it into several non-overlapping fragments. Each of the fragments will be a horizontal or vertical strip containing 1 or more elements. A strip of length N can be interpreted as an N-digit number in base 10 by concatenating the digits on the strip in order. The horizontal strips are read from left to right and the vertical strips are read from top to bottom. The picture below shows a possible cutting of a 4x4 board:
The sum of the numbers on the fragments in this picture is 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879.
Manao wants to cut the board in such a way that the sum of the numbers on the resulting fragments is the maximum possible. Compute and return this sum.
Definition
- Class:
- CutTheNumbers
- Method:
- maximumSum
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int maximumSum(String[] board)
- (be sure your method is public)
Notes
- The numbers on the cut strips are allowed to have leading zeros. See example #2 for details.
Constraints
- board will contain between 1 and 4 elements, inclusive.
- board[0] will be between 1 and 4 characters long, inclusive.
- Each element of board will be of the same length as board[0].
- Each character in board will be a decimal digit ('0'-'9').
Examples
{"123", "312"}
Returns: 435
Manao can cut out both rows in whole, obtaining 123 + 312 = 435. He also could cut the columns one by one for a total of 66, or cut the first column and the residual rows one by one, obtaining 13 + 23 + 12 = 48, or even cut out single elements, but would not get a better sum.
{"99", "11"}
Returns: 182
It's better to cut out the whole columns.
{"001", "010", "111", "100"}
Returns: 1131
The numbers on the strips may have leading zeros. Cutting the columns in whole, Manao obtains 0011 + 0110 + 1010 = 1131.
{"8"}
Returns: 8
{"0011", "0011", "0011", "1111"}
Returns: 2233
{"0002","0101","1011","0202"}
Returns: 2243
{"0001","0000","1011","2002"}
Returns: 3023
{"0002","0011","0012","2210"}
Returns: 2433
{"0011","0001","1021","2021"}
Returns: 3063
{"0020","0011","0002","2211"}
Returns: 2433
{"0011","0102","0101","2110"}
Returns: 2342
{"0021","0000","0012","2201"}
Returns: 3053
{"0020","0011","0000","1002"}
Returns: 2212
{"0"}
Returns: 0
{"0000"}
Returns: 0
{"9999"}
Returns: 9999
{"9999","9999","9999","9999"}
Returns: 39996
{"0341","5155","7470","6513"}
Returns: 19479
{"0003","0121","0032","3122"}
Returns: 3467
{"2003","1002","0103","1201"}
Returns: 5362
{"0023","0020","0230","3200"}
Returns: 5264
{"0000","0001","0002","1022"}
Returns: 1034
{"0013","0022","3111","2203"}
Returns: 5358
{"2220","0012","0011"}
Returns: 2252
{"1200","0002","0001"}
Returns: 1221
{"2020","0012","0002"}
Returns: 2052
{"2000","0022","0010"}
Returns: 2041
{"2202","0002","0010"}
Returns: 2223
{"0022","0011","1002"}
Returns: 1044
{"0002","0012","2210"}
Returns: 2233
{"1211","0012","0010"}
Returns: 1242
{"002","001","202","211"}
Returns: 2162
{"100","000","001","020"}
Returns: 1021
{"001","000","000","222"}
Returns: 1024
{"009","013","888"}
Returns: 1027
{"009","322","605"}
Returns: 1017
{"003","108","269"}
Returns: 425
{"027","017","996"}
Returns: 1094
{"082","000","952"}
Returns: 1052
{"015","026","929"}
Returns: 997
{"044","038","863"}
Returns: 954
{"027","010","984"}
Returns: 1075
{"009","331","533"}
Returns: 999
{"007","219","474"}
Returns: 862
{"013","003","938"}
Returns: 981
{"008","142","746"}
Returns: 914
{"005","020","890"}
Returns: 942
{"002","008","481"}
Returns: 509
{"008","126","690"}
Returns: 941
{"041","004","576"}
Returns: 630
{"004","019","719"}
Returns: 769
{"002","011","823"}
Returns: 845
{"009","400","573"}
Returns: 1000
{"004","015","632"}
Returns: 678
{"042","012","791"}
Returns: 854
{"007","215","466"}
Returns: 823
{"004","009","252"}
Returns: 517
{"041","009","956"}
Returns: 1015
{"026","043","817"}
Returns: 904
{"008","145","688"}
Returns: 940
{"042","016","638"}
Returns: 705
{"007","316","417"}
Returns: 839
{"004","028","886"}
Returns: 936
{"052","017","803"}
Returns: 881
{"005","126","376"}
Returns: 615
{"018","044","908"}
Returns: 1006
{"008","337","619"}
Returns: 973
{"007","109","688"}
Returns: 876
{"006","102","374"}
Returns: 671
{"026","008","891"}
Returns: 979
{"034","035","781"}
Returns: 859
{"003","010","763"}
Returns: 794
{"027","015","900"}
Returns: 996
{"005","134","448"}
Returns: 605
{"007","220","304"}
Returns: 756
{"044","022","933"}
Returns: 1017
{"007","022","879"}
Returns: 953
{"037","007","997"}
Returns: 1104
{"041","003","563"}
Returns: 616
{"034","039","849"}
Returns: 931
{"007","110","337"}
Returns: 751
{"009","304","320"}
Returns: 1002
{"006","048","650"}
Returns: 749
{"008","142","626"}
Returns: 902
{"009","024","507"}
Returns: 999
{"004","037","426"}
Returns: 521
{"033","025","643"}
Returns: 710
{"052","008","871"}
Returns: 949
{"043","017","971"}
Returns: 1049
{"022","015","513"}
Returns: 559
{"032","017","880"}
Returns: 938
{"006","025","911"}
Returns: 978
{"009","413","523"}
Returns: 1026
{"009","016","379"}
Returns: 1007
{"008","014","685"}
Returns: 914
{"045","002","860"}
Returns: 952
{"005","100","132"}
Returns: 525
{"002","008","881"}
Returns: 909
{"004","209","195"}
Returns: 534
{"007","224","389"}
Returns: 809
{"023","006","550"}
Returns: 606
{"015","004","699"}
Returns: 763
{"021","001","440"}
Returns: 471
{"004","123","310"}
Returns: 473
{"002","101","100"}
Returns: 230
{"001","000","320"}
Returns: 330
{"002","101","103"}
Returns: 233
{"022","013","432"}
Returns: 476
{"004","204","232"}
Returns: 485
{"001","000","110"}
Returns: 120
{"001","000","100"}
Returns: 110
{"001","001","101"}
Returns: 121
{"001","000","111"}
Returns: 121
{"0018","0026","7020"}
Returns: 7118
{"5325","1242"}
Returns: 6567
{"1","2","3","1"}
Returns: 1231
{"001","002","301","302"}
Returns: 1272
{"200","200","010","311"}
Returns: 2224
{"002","004","021","443"}
Returns: 2459
{"100","200","331","230"}
Returns: 1293
{"372"}
Returns: 372
{"2","4","6"}
Returns: 246
{"9","1","8","6"}
Returns: 9186
{"403","027","245"}
Returns: 801
{"569","339","053","679"}
Returns: 21602
{"27","19"}
Returns: 100
{"24"}
Returns: 24
{"8761"}
Returns: 8761
{"975","656","271"}
Returns: 2280
{"188","964"}
Returns: 1152
{"175"}
Returns: 175
{"8769","3043","3841","7303"}
Returns: 31173
{"9","8"}
Returns: 98
{"0679","5936"}
Returns: 6615
{"21"}
Returns: 21
{"1855","3436","5720"}
Returns: 11011
{"8","9","9","5"}
Returns: 8995
{"9006","0211"}
Returns: 9217
{"0264","7702","5816","5552"}
Returns: 19334
{"8","8","2","4"}
Returns: 8824
{"9289","4508","6731"}
Returns: 20528
{"8","1","6"}
Returns: 816
{"576"}
Returns: 576
{"755","523","389"}
Returns: 1820
{"710","778","716"}
Returns: 2204
{"6","5","5"}
Returns: 655
{"9322"}
Returns: 9322
{"6392","2555","6517"}
Returns: 15464
{"317","111"}
Returns: 428
{"83","72"}
Returns: 155
{"517","919","840"}
Returns: 2276
{"995","586"}
Returns: 1581
{"8"}
Returns: 8
{"294","431","599"}
Returns: 1603
{"09","48"}
Returns: 102
{"01","83","04"}
Returns: 214
{"55","84"}
Returns: 139
{"584","925","839","839"}
Returns: 18820
{"62","51","30"}
Returns: 863
{"571"}
Returns: 571
{"6750"}
Returns: 6750
{"97"}
Returns: 97
{"17"}
Returns: 17
{"8666","7620","8661"}
Returns: 24947
{"0403","0343"}
Returns: 746
{"529","689","216","038"}
Returns: 18401
{"730","159","385","183"}
Returns: 11672
{"30","31","95"}
Returns: 354
{"32"}
Returns: 32
{"9418","4862"}
Returns: 14280
{"5","4"}
Returns: 54
{"8","7"}
Returns: 87
{"5","2"}
Returns: 52
{"5372","3704","2834","4080"}
Returns: 18582
{"59","53","95","06"}
Returns: 14946
{"0212"}
Returns: 212
{"4"}
Returns: 4
{"68","14"}
Returns: 145
{"9","6","8","9"}
Returns: 9689
{"2","4","6"}
Returns: 246
{"20"}
Returns: 20
{"1485","4766","2590","7677"}
Returns: 20487
{"4805","9760"}
Returns: 14565
{"07","64","83","28"}
Returns: 8120
{"2","5","2"}
Returns: 252
{"74","84"}
Returns: 158
{"499"}
Returns: 499
{"4608","8295"}
Returns: 12903
{"55"}
Returns: 55
{"9","4","7"}
Returns: 947
{"5060","9149"}
Returns: 14209
{"19","08","40","83"}
Returns: 10851
{"36","98","48","35"}
Returns: 10828
{"794","708","850"}
Returns: 2352
{"7785","2218","2406"}
Returns: 12409
{"411","028","277","394"}
Returns: 7176
{"6658","1220"}
Returns: 7878
{"3"}
Returns: 3
{"4850","0082","5473"}
Returns: 10405
{"95","05","43"}
Returns: 1457
{"3572","9386","8698"}
Returns: 21656
{"71"}
Returns: 71
{"14","98"}
Returns: 112
{"3002"}
Returns: 3002
{"07","75"}
Returns: 82
{"9281","3409","6814"}
Returns: 19504
{"88","96","68","27"}
Returns: 17649
{"514","984"}
Returns: 1498
{"0022","0011","0030","1000"}
Returns: 4240
{"0003","0012","2122","0012"}
Returns: 3436
{"0023","0013","1231","3311"}
Returns: 5487
{"0031","0030","1030","2000"}
Returns: 4360
{"0012","0013","1033","3212"}
Returns: 4279
{"0033","0033","2003","1230"}
Returns: 6665
{"0021","0022","1023","2013"}
Returns: 3484
{"0020","0020","0021","3012"}
Returns: 3235
{"0110","0102","0001","2201"}
Returns: 2432
{"0003","1010","0003","1321"}
Returns: 3264
{"0003","0113","3223","0003"}
Returns: 3666
{"0102","0102","0022","3122"}
Returns: 3456
{"0003","1011","1122","1013"}
Returns: 3437
{"0001","0002","1231","1111"}
Returns: 2354
{"0003","0210","0021","3300"}
Returns: 3633
{"0020","0001","1003","1010"}
Returns: 2151
{"0003","0020","3023","0320"}
Returns: 3375
{"0032","0032","0100","2120"}
Returns: 5524
{"8" }
Returns: 8
{"009", "219", "219" }
Returns: 1041
{"0009", "1111", "4111", "1111" }
Returns: 9744
{"0001", "0001", "0001", "1111" }
Returns: 1222
{"001", "000", "000", "990" }
Returns: 1099
{"123", "312" }
Returns: 435
{"0009", "0008", "0009", "0199" }
Returns: 9918
{"0099", "0090", "0000", "9010" }
Returns: 18991
{"3003", "2004", "1112", "0340" }
Returns: 6675
{"1000", "0001", "0000" }
Returns: 1010
{"9026", "0018", "9978", "0999" }
Returns: 20021
{"0088", "0000", "0000", "9000" }
Returns: 16090
{"001", "010", "111", "100" }
Returns: 1131
{"0009", "0009", "1234", "0000" }
Returns: 10063
{"001", "000", "001", "110" }
Returns: 1021
{"0009", "2112", "2114", "2112" }
Returns: 9875
{"009", "009", "999" }
Returns: 1098
{"001", "000", "000", "661" }
Returns: 1067
{"1000", "0099", "0000", "1100" }
Returns: 2811
{"0001", "0001", "0001" }
Returns: 111
{"001", "000", "100" }
Returns: 110
{"0009", "0000", "0000", "0990" }
Returns: 9099
{"0009", "0000", "0000", "9990" }
Returns: 10890
{"9308", "4076", "9490", "5561" }
Returns: 28435
{"0009", "0000", "2000", "2000" }
Returns: 9400
{"1000", "0099", "0000" }
Returns: 1180
{"009", "009", "789" }
Returns: 1077
{"0020", "0001", "0213", "0821" }
Returns: 2171
{"012", "009" }
Returns: 39
{"9000", "0001", "0001" }
Returns: 9011
{"0007", "0001", "0006", "9150" }
Returns: 9866
{"0001", "0003", "0004", "0220" }
Returns: 1362
{"0009", "0009", "0009", "0999" }
Returns: 10098
{"009", "009", "009", "999" }
Returns: 10098
{"0009", "0009", "0009", "0119" }
Returns: 10010
{"0020", "0010", "0000", "2000" }
Returns: 2210
{"0001", "0001", "0110" }
Returns: 121
{"0001", "0000", "9000", "0000" }
Returns: 9010
{"001", "001", "999" }
Returns: 1010
{"0001", "0000", "0000", "9999" }
Returns: 10099
{"0009", "0000", "0000", "1000" }
Returns: 9100
{"0001", "0000", "0000", "1000" }
Returns: 1100