lehrkraefte:blc:informatik:ffprg2-2024:longest-increasing-subsequence [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Erster längster aufsteigender Abschnitt ======
Gegeben ist eine Folge von $n$ unterschiedlichen Zahlen. Gesucht ist die Länge und der Startindex (0-basiert) des ersten, längsten aufsteigenden Abschnitts (d.h. aufeinanderfolgende Elemente sind aufsteigend geordnet).

Die Eingabe enthält in der ersten Zeile die Anzahl Testfälle $T$.

Für jeden Testfall ist in einer Zeile die Anzahl Folgeglieder $n$ gegeben und in der nächsten Zeile alle Folgeglieder durch Leerschläge getrennt.

Input:
<code text>
4
10
5 7 9 3 2 6 1 0 4 8
100
77 39 38 33 80 19 98 23 91 45 72 28 25 27 53 74 36 22 61 85 21 14 6 69 79 99 84 93 96 30 17 4 34 90 13 71 3 62 86 55 12 35 18 59 20 66 54 50 15 87 43 42 11 76 52 94 41 46 60 44 47 40 5 37 68 67 89 70 63 57 32 64 49 88 31 65 8 78 75 97 1 81 24 73 10 9 95 48 92 7 83 26 58 82 0 56 51 16 29 2
200
15 51 197 165 7 46 122 172 191 113 87 74 177 67 104 78 103 128 189 196 133 141 155 153 66 178 3 163 195 4 138 114 12 135 30 179 34 173 94 147 68 62 157 168 190 35 42 170 183 134 137 82 144 47 98 31 127 116 32 162 70 17 81 142 176 136 90 43 166 29 175 148 107 193 160 181 97 130 140 118 52 132 101 184 110 57 28 83 23 37 36 79 75 99 59 63 14 49 167 187 159 123 108 39 2 185 64 20 100 9 40 96 169 41 92 44 124 199 19 111 119 126 102 80 120 21 85 143 55 71 88 188 95 73 56 5 164 194 27 109 171 182 24 129 105 54 48 8 121 93 117 145 150 198 152 18 69 186 125 131 156 1 106 161 16 45 58 91 33 76 158 149 115 112 0 192 6 72 50 154 77 53 84 89 65 151 174 146 26 139 38 25 61 22 60 86 11 10 180 13
1000
53 546 537 666 63 598 335 251 419 734 878 151 805 362 36 709 599 27 117 809 996 155 245 620 77 93 499 235 457 256 275 936 543 131 725 359 858 607 603 772 120 468 816 994 489 558 48 109 703 552 662 870 492 990 453 103 753 759 23 651 929 887 872 323 813 75 360 223 672 132 249 726 428 625 630 609 621 322 294 821 157 738 570 776 534 70 282 314 784 946 926 824 818 126 871 222 310 900 267 729 475 458 778 307 479 688 333 687 381 812 483 374 166 997 535 495 435 473 6 12 434 500 610 202 420 449 920 982 981 71 192 823 301 102 82 385 284 869 487 829 948 910 974 397 83 210 790 200 697 780 328 24 631 334 933 857 896 255 331 877 51 133 563 40 811 988 695 104 190 888 606 8 455 73 2 762 999 661 581 628 850 1 716 344 751 533 232 673 325 68 422 354 679 979 365 551 675 932 862 252 627 276 265 4 170 13 965 329 577 616 106 228 45 10 292 749 478 85 715 371 5 640 352 330 105 201 576 646 175 635 205 702 414 37 462 819 98 714 993 689 91 402 848 47 165 485 592 668 983 432 680 184 851 895 894 658 971 469 808 705 970 885 297 961 605 804 355 579 253 602 366 721 967 33 59 696 309 682 539 655 583 215 391 189 351 264 439 836 636 183 219 781 565 46 586 856 837 617 399 39 452 957 864 28 415 521 556 161 211 789 115 761 987 791 76 81 588 84 145 124 739 914 384 938 792 99 865 480 685 575 782 289 237 216 174 860 774 611 305 671 720 403 587 488 641 411 954 785 660 873 833 712 341 882 807 208 444 107 913 745 125 755 919 555 320 973 732 574 430 624 841 135 806 321 242 834 116 623 674 258 193 835 149 786 97 918 822 608 707 206 523 392 719 670 440 217 304 614 113 524 380 464 849 268 518 855 964 16 241 931 799 62 904 502 156 160 771 503 470 340 67 129 142 868 969 388 980 29 345 229 400 923 958 375 743 866 959 423 19 150 447 34 978 589 797 497 136 220 710 21 225 522 148 648 509 568 951 58 903 912 733 463 110 199 831 246 907 909 90 443 31 532 750 94 861 395 474 445 612 915 615 730 706 186 905 678 164 187 573 632 788 236 79 955 541 676 513 536 128 763 451 569 481 937 364 578 590 826 863 383 450 642 394 992 266 298 501 370 418 339 191 221 123 724 393 482 248 741 356 505 315 281 595 404 561 692 213 940 57 748 814 269 185 798 810 775 899 424 508 754 886 562 119 708 650 92 795 711 995 286 653 663 768 456 787 426 941 731 431 922 777 373 504 669 60 934 713 244 436 800 917 153 377 278 446 154 840 604 976 396 968 972 337 991 801 846 296 828 134 935 410 146 7 101 690 263 293 802 239 736 65 737 652 752 401 897 448 902 295 656 906 285 803 122 406 460 723 179 342 25 427 832 35 188 346 486 756 867 985 820 531 883 493 49 442 718 859 773 647 350 114 287 898 704 100 177 112 429 353 542 760 530 203 433 243 111 95 510 141 326 196 633 471 176 916 198 159 664 507 311 127 728 147 793 379 845 659 639 629 686 643 984 548 313 927 963 250 476 949 783 20 977 369 459 525 842 180 619 74 257 645 218 372 557 890 262 56 348 744 654 421 413 144 438 363 88 61 367 317 838 827 491 694 515 908 854 69 224 520 44 830 540 852 319 197 747 580 80 209 591 699 698 596 382 944 327 526 844 461 945 758 626 506 942 52 735 634 0 279 182 407 171 163 950 270 517 277 494 722 547 597 496 930 72 875 465 299 288 893 172 357 227 467 96 960 376 952 684 316 169 108 38 825 564 15 618 815 303 87 757 559 638 214 742 66 207 740 64 477 544 889 613 167 554 378 290 560 956 817 683 989 204 571 405 943 876 901 230 746 584 839 962 764 770 553 892 195 168 512 398 928 162 173 425 390 143 302 389 306 22 884 336 794 572 765 231 194 528 130 338 514 921 677 545 139 238 966 42 254 874 986 601 386 567 644 939 324 527 32 701 585 767 891 649 881 511 582 261 43 667 847 691 550 416 118 717 924 484 953 387 137 14 272 498 880 260 409 657 600 54 273 121 779 233 454 332 178 280 637 769 11 490 3 681 9 796 181 50 693 283 519 925 89 140 566 271 259 274 529 538 417 86 212 26 594 152 347 78 727 358 441 593 766 408 158 911 30 240 975 843 853 472 41 368 466 308 234 138 247 516 412 437 55 17 349 18 300 549 665 318 291 343 998 879 312 226 947 361 622 700
</code>

Output:
<code text>
Case #0: length 3 starts at index 0
Case #1: length 4 starts at index 12
Case #2: length 5 starts at index 4
Case #3: length 7 starts at index 632
</code>


====== Erwartungswert bei zufälliger Liste ======
In welcher Grössenordnung wird wohl der Erwartungswert liegen? Begründen Sie.


====== Bonus: Längste aufsteigende Unterfolge ======
Die Elemente müssen nun nicht mehr hintereinander sein. Gesucht ist die Länge der längsten aufsteigenden Unterfolge (die Elemente werden in der Reihenfolge ausgewählt, wie sie in der Liste erscheinen, müssen aber nicht mehr benachbart sein).

Mit gleicher Eingabe ist die Ausgabe folgende:
<code text>
Case #0: 3
Case #1: 16
Case #2: 26
Case #3: 58
</code>