추가로 제가 찾은 예제입니다.
10
574 155 634 519 872 391 918 240 108 96
7
10
504 323 266 170 295 449 653 323 12 365
6
10
747 825 519 207 565 304 568 868 82 641
5
10
506 937 503 144 738 70 59 684 332 75
6
10
142 869 487 753 862 797 232 363 556 138
7
10
178 91 593 601 77 33 737 774 333 280
7
10
613 115 659 382 934 134 871 433 201 137
7
10
785 199 935 455 869 681 274 3 41 957
6
10
306 271 803 552 668 306 174 762 12 516
6
10
927 114 235 558 946 120 176 520 653 834
6
10
227 288 896 458 557 11 650 192 434 185
7
7
485 456 214 258 267 593 43
5
1000
574 155 634 519 872 391 918 240 108 96 504 323 266 170 295 449 653 323 12 365 747 825 519 207 565 304 568 868 82 641 506 937 503 144 738 70 59 684 332 75 142 869 487 753 862 797 232 363 556 138 178 91 593 601 77 33 737 774 333 280 613 115 659 382 934 134 871 433 201 137 785 199 935 455 869 681 274 3 41 957 306 271 803 552 668 306 174 762 12 516 927 114 235 558 946 120 176 520 653 834 227 288 896 458 557 11 650 192 434 185 485 456 214 258 267 593 43 716 49 96 464 306 491 455 260 744 225 998 542 457 705 977 209 912 666 556 320 694 832 133 32 259 422 327 210 255 192 680 650 366 84 645 21 920 886 148 379 209 260 479 341 482 408 469 458 783 335 100 535 658 415 350 380 0 234 416 366 37 579 659 798 413 519 111 376 893 492 660 903 730 290 411 265 751 383 396 904 819 666 176 512 679 640 308 407 184 923 427 231 141 428 996 178 632 735 723 458 381 931 455 141 842 316 879 625 38 631 223 857 414 898 249 562 293 888 92 805 728 727 968 878 342 980 155 102 798 733 945 959 160 583 761 406 940 720 108 350 501 772 797 389 105 31 546 996 276 779 310 884 645 409 503 855 415 615 604 881 828 753 242 188 386 689 281 7 941 741 185 132 294 807 963 50 668 688 151 123 164 314 666 335 233 209 118 615 277 955 568 443 497 176 462 77 595 249 624 256 620 380 956 663 574 737 806 913 638 629 912 637 352 495 5 89 507 128 40 708 704 380 132 862 962 4 69 698 562 265 493 844 753 19 265 491 877 182 553 906 791 714 673 847 757 942 556 457 764 167 354 444 851 131 143 447 377 477 530 360 443 357 115 700 876 518 580 689 597 144 289 340 282 324 520 63 153 655 402 510 17 947 906 896 874 209 66 749 519 976 70 614 394 907 957 516 144 18 365 186 891 624 241 908 649 461 299 598 698 255 9 798 805 848 541 993 548 615 748 219 924 120 395 531 190 534 482 603 715 1000 86 675 294 241 113 538 285 364 857 761 546 124 224 11 281 110 345 45 410 349 33 408 366 913 111 803 749 860 157 271 362 604 971 465 964 998 513 303 108 415 277 863 473 502 893 462 984 736 545 365 235 32 628 6 383 973 924 598 464 885 209 212 242 71 102 487 674 513 144 753 513 615 788 595 396 770 99 841 306 725 606 643 179 666 138 325 750 682 58 369 873 610 723 356 892 22 328 813 962 169 234 959 35 203 854 888 329 548 71 77 405 78 613 809 779 250 269 55 622 280 982 427 750 36 925 13 705 839 113 372 221 206 629 851 832 562 941 813 189 838 894 483 197 798 793 554 809 25 628 127 155 149 158 321 632 404 519 876 599 140 304 476 370 5 32 740 677 692 514 920 752 259 412 129 697 122 611 570 425 754 919 852 887 910 435 123 294 475 733 253 969 929 366 816 803 187 52 317 727 833 420 900 553 814 92 566 201 434 533 406 784 675 368 920 210 562 277 144 893 489 31 457 731 824 765 702 436 753 393 894 518 366 124 63 368 502 161 865 725 353 24 754 660 790 442 642 282 727 150 314 583 66 261 798 280 827 346 64 665 703 281 780 826 913 473 102 973 325 323 575 184 881 312 304 971 99 606 329 19 405 281 705 521 970 888 586 153 939 576 595 25 277 182 906 806 473 312 947 283 523 805 769 975 637 481 368 110 224 706 292 817 217 374 866 863 438 376 513 125 160 300 985 674 858 943 343 614 48 346 287 695 477 71 757 12 3 377 876 616 165 207 222 830 926 36 869 764 92 192 509 733 732 985 163 385 445 647 403 406 879 182 435 744 808 589 469 73 220 466 518 262 304 957 49 595 389 973 644 1000 695 563 265 751 34 475 442 315 660 141 635 338 726 906 701 586 516 584 216 933 669 594 606 205 500 38 84 888 609 409 883 106 485 573 92 335 689 857 512 0 122 272 491 566 830 982 395 997 603 761 70 126 970 226 831 601 134 299 18 864 967 431 515 240 83 68 921 22 696 356 303 216 214 505 521 865 191 637 829 512 689 346 962 811 123 829 742 986 589 585 162 59 82 265 232 796 872 515 822 207 56 58 888 118 175 305 416 390 431 957 312 527 775 806 200 761 751 247 411 134 723 742 827 870 958 377 345 690 851 759 106 807 391 810 815 863 768 519 868 679 311 787 918 959 862 605 478 132 233 328 149 203 918 474 322 831 212 232 545 698 260 265 324 215 701 75 156 605 851 993 425 887 691 593
87
dksdmssh1212 3년 전 26
알고리즘은 이렇습니다.
dp_ascending[i] = 1번부터 i번째 수 까지 최대길이 증가 부분수열
dp_descending[i] = i번째 수부터 N번째 수 까지 최대길이 감소 부분수열
dp_bitonic[i] = dp_ascending[i] + dp_descending[i+1]
(i번째 까지 증가하고 i+1번째 부터 감소하는 수열)
마지막에는 dp_bitonic의 최댓값을 구했습니다.
만약
2
1 1
과 같이 두 수가 같은 경우에 대한 예외처리는
i번째 수와 i+1번째 수가 같을 경우 dp_ascending[i]와 dp_descending[i]의 값의 max값으로 결정했습니다.
17
7 2 1 1 5 2 2 3 2 3 1 2 4 5 1 2 4
정답 6
10
1 5 2 1 4 3 4 5 2 1
정답 7
5
1 2 3 2 1
정답 5
6
1 2 3 5 5 1
정답 5
5
1 2 1 1 1
정답 3
2
999 1000
정답 2
6
1 2 3 3 2 1
정답 5
5
1 3 1 2 1
정답 4
5
1 5 4 2 3
정답 4
7
5 1 6 2 6 2 1
정답 5
9
5 1 6 2 7 3 7 2 1
정답 6
4
1 2 2 1
정답 3
6
1 2 3 2 1 4
정답 5
2
1 1
정답 1
4
1 1 2 1
정답 3
5
5 4 3 2 3
정답 4