CT29085

Last stairwells of Bhavi

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Bhavi runs the apothecary at the lantern reef of Glowtide. Today the books show a list of stairwells, and the numbers must be worked out before sundown. Task: Choose a subset of the n values so no two chosen values are adjacent; print the maximum achievable sum. Input format: First line: n. Second line: n nonnegative integers. Output format: Print the maximum sum. Constraints: 1 <= n <= 4000; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1372 969231543 130521555 743610585 642823602 795593798 308836526 720607665 443840451 582412230 195640828 887013786 978320871 313886070 45372512 895493874 382531146 730628884 802618163 177844372 66070562 798611759 320317339 487037965 889353302 204482941 404739676 877359823 387758696 321597687 889618387 778335763 218628421 607433158 414461984 695829369 336485442 322365882 366799025 359349823 758635110 457454113 318274547 921111214 341964343 686241605 240069702 101861844 270424055 267159307 912486139 594429622 488855569 658153426 688192128 947897385 106204041 403620223 707982096 592404186 821065850 391549911 455205915 366899791 775173584 187029187 320463256 734137620 985727189 952563708 422779232 86987726 811034519 609206708 745573016 492240044 310421963 715353802 359133375 210081594 72214430…
Output: 404699261937

Example 2:

Input: 2281 308179305 912887446 806663275 427306758 919008906 82633379 542979605 843562682 488995871 223573853 296834496 846135005 115387198 763909440 458469733 238575944 926870144 633780462 238685526 73483489 543194925 128127670 296709503 999450701 295267015 984671768 599311959 218810140 28992615 245678745 956470560 244983520 937675436 709809437 150225680 748970974 513245747 863548829 791144830 812847336 390129804 882464385 194797659 643289190 194732852 329186667 447494771 651392399 143111427 409499649 922700611 33260707 622585445 937430106 576104650 895099523 581736971 709870785 83532485 343540089 801687896 790524667 470339263 630258154 591760660 409654752 819441589 947891321 455091753 192589645 806140246 771785572 286494476 446750787 171602291 797703825 869324049 427648932 643468720 730682720 …
Output: 675769190422

Example 3:

Input: 2979 244372155 499127159 745057439 888797695 884250433 409410334 712124859 945722271 618792523 79761995 863005709 919735560 931971371 960201773 375236180 122132399 818508962 226053272 71063930 862416798 330024070 365103703 931847175 63572032 570440869 47583942 879089866 726794435 251741923 364535060 403096321 89153079 894336780 412251417 111115732 84421224 652090647 190034240 798989329 589820761 64202579 25881307 458169189 75383939 230762058 809055108 452517904 271999252 251905172 838967164 433164776 211290321 884279705 696970900 267620358 407940281 166703389 290980282 237528975 348502111 646263188 731727064 969593583 893526758 376455633 51167850 559316811 427249762 245226091 701441828 932869019 353800085 24211782 345696135 466555471 4409241 283754996 198971700 550504552 217749645 90675434…
Output: 882246633275

Constraints:

1 <= n <= 4000; 0 <= a[i] <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
Last stairwells of Bhavi - MEDIUM Coding Problem | CodeTikki