[0]zero-index clytie0x/zero-index

25.2 LIS ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด

น้องสอบย่อยวิชาคณิตศาสตร์ 8 ครั้ง ได้คะแนน 5 2 8 6 3 6 9 7 อยากเลือกบางครั้งมาเรียงตามเวลาให้เห็นว่าคะแนน สูงขึ้นทุกครั้ง ได้ยาวที่สุดกี่ครั้ง คำถามนี้ชื่อ LIS ย่อมาจาก longest increasing subsequence แปลว่าลำดับย่อยที่เพิ่มขึ้นยาวที่สุด เจอบ่อยในค่าย 2 ทั้งแบบตรงๆ และแบบซ่อน เช่น ซ้อนกล่อง เรียงคนตามความสูง หรือหาจำนวนครั้งน้อยสุดที่ต้องย้ายของให้เรียง หน้านี้เริ่มจาก DP แบบ O(N2) ที่คิดตามบทที่ 24 ตรงๆ แล้วเร่งเป็น O(N log N) ด้วย lower_bound จากบทที่ 19 พร้อมพิมพ์ลำดับจริงออกมา

ลำดับย่อยไม่ใช่ช่วงติดกัน

ลำดับย่อย (subsequence) คือเลือกบางตัวโดยคงลำดับเดิมไว้ ข้ามตัวไหนก็ได้ ต่างจาก ช่วง (subarray) ในโจทย์ Kadane ของบทที่ 24 ที่ต้องติดกัน จากคะแนนข้างบน 2 3 6 9 เป็นลำดับย่อยที่เพิ่มขึ้น เพราะ 2 อยู่ครั้งที่ 2 ส่วน 3 6 9 อยู่ครั้งที่ 5 6 7 ตามลำดับ แต่ 2 3 6 8 ไม่ใช่ เพราะ 8 อยู่ครั้งที่ 3 ก่อน 3 กับ 6 ส่วน "เพิ่มขึ้น" ในหน้านี้หมายถึง มากกว่าตัวก่อนหน้าจริงๆ คะแนนเท่ากันไม่นับ

ลำดับยาว N มีลำดับย่อย 2N แบบ ลองทุกแบบไม่ไหว

DP แบบ O(N2)

ให้ length[i] คือความยาวของลำดับย่อยที่เพิ่มขึ้นที่ยาวที่สุดที่ จบที่ตัวที่ i พอดี การบังคับให้จบที่ i ทำให้รู้ว่าตัวสุดท้ายคือ a[i] ตัวก่อนหน้ามันจึงเป็น a[j] ตัวไหนก็ได้ที่ j < i และ a[j] < a[i] เลือกตัวที่ length[j] มากที่สุดแล้วต่อท้ายด้วย a[i] ถ้าไม่มี j แบบนั้นเลย ลำดับมีแค่ a[i] ตัวเดียว ยาว 1 คำตอบคือ length[i] ที่มากที่สุดในทุก i

จดว่าแต่ละตัวต่อมาจากตัวไหนไว้ใน previous[i] แบบการเก็บเส้นทางย้อนกลับในบทที่ 24 จะพิมพ์ลำดับจริงได้

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> length(n, 1), previous(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && length[j] + 1 > length[i]) { // (1)!
                length[i] = length[j] + 1;
                previous[i] = j;
            }
        }
    }
    int last = 0;
    for (int i = 0; i < n; i++) {
        cout << "i=" << i << " a=" << a[i] << " length=" << length[i] << " previous=" << previous[i] << '\n';
        if (length[i] > length[last]) {
            last = i;
        }
    }
    vector<int> sequence;
    for (int i = last; i != -1; i = previous[i]) {
        sequence.push_back(a[i]);
    }
    reverse(sequence.begin(), sequence.end());
    cout << "LIS length = " << sequence.size() << '\n';
    for (int k = 0; k < (int)sequence.size(); k++) {
        cout << sequence[k] << (k + 1 == (int)sequence.size() ? '\n' : ' ');
    }
    return 0;
}
  1. เงื่อนไข > ทำให้ previous[i] เก็บ j ตัวแรกที่ให้ความยาวมากสุด ถ้าเปลี่ยนเป็น >= ความยาวยังเท่าเดิม แต่ลำดับที่พิมพ์อาจเปลี่ยนไป
8
5 2 8 6 3 6 9 7

i=0 a=5 length=1 previous=-1
i=1 a=2 length=1 previous=-1
i=2 a=8 length=2 previous=0
i=3 a=6 length=2 previous=0
i=4 a=3 length=2 previous=1
i=5 a=6 length=3 previous=4
i=6 a=9 length=4 previous=5
i=7 a=7 length=4 previous=5
LIS length = 4
2 3 6 9

โปรแกรมนับตำแหน่งจาก 0 ดูบรรทัด i=6 คือคะแนน 9 ตัวก่อนหน้าน้อยกว่า 9 ทุกตัว ตัวที่ยาวที่สุดคือ i=5 (คะแนน 6) ยาว 3 จึงได้ 4 ย้อนจาก i=6 ไป i=5 i=4 และ i=1 ได้ 9 6 3 2 กลับลำดับเป็น 2 3 6 9 บรรทัด i=7 (คะแนน 7) ก็ยาว 4 เหมือนกัน แปลว่า 2 3 6 7 ก็เป็นคำตอบได้ LIS มักมีหลายแบบ โจทย์ที่ให้พิมพ์ลำดับจึงต้องบอกว่าเอาแบบไหน หรือยอมรับแบบไหนก็ได้

ทุก i ไล่ j ทุกตัวก่อนหน้า รวม N(N - 1)/2 คู่ เป็น O(N2) N เป็นหมื่นยังไหว แต่ N เป็นแสนไม่ทัน ซึ่งจะเห็นในตารางเวลาท้ายหน้า

เก็บหางที่เล็กที่สุดของแต่ละความยาว

เปลี่ยนมุมมอง ไล่ตัวเลขจากซ้ายไปขวา แล้วถามว่า ลำดับย่อยที่เพิ่มขึ้นยาว k ที่เจอมาแล้ว ตัวสุดท้ายเล็กได้แค่ไหน เก็บคำตอบไว้ใน tails[k - 1] เหตุผลคือ ถ้ามีลำดับยาวเท่ากันสองแบบ แบบที่จบด้วยตัวเล็กกว่าดีกว่าเสมอ เพราะตัวเลขที่จะมาต่อท้ายได้ในอนาคต ต่อแบบที่หางใหญ่ได้ ก็ต่อแบบที่หางเล็กได้แน่นอน

tails เรียงจากน้อยไปมากเสมอ (ลำดับยาว k + 1 มีส่วนต้นยาว k ที่จบด้วยตัวที่น้อยกว่าหางของมัน) จึงใช้ binary search ได้ พอเจอตัวเลข x ใหม่

  • หาช่องแรกใน tails ที่ >= x ด้วย lower_bound สมมติว่าเป็นช่อง pos
  • ทุกช่องก่อน pos มีหางน้อยกว่า x จึงต่อ x ท้ายลำดับยาว pos ได้ กลายเป็นลำดับยาว pos + 1 ที่หางคือ x
  • ถ้า pos เลยท้าย tails แปลว่าได้ลำดับที่ยาวกว่าที่เคยมี ต่อท้าย tails ถ้าไม่ ให้ทับ tails[pos] ด้วย x ซึ่งเล็กกว่าหรือเท่าของเดิม
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> tails;
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(tails.begin(), tails.end(), a[i]) - tails.begin();
        if (pos == (int)tails.size()) {
            tails.push_back(a[i]);
        } else {
            tails[pos] = a[i];
        }
        cout << "a=" << a[i] << " pos=" << pos << " tails:";
        for (int k = 0; k < (int)tails.size(); k++) {
            cout << ' ' << tails[k];
        }
        cout << '\n';
    }
    cout << "LIS length = " << tails.size() << '\n';
    return 0;
}

8
5 2 8 6 3 6 9 7

a=5 pos=0 tails: 5
a=2 pos=0 tails: 2
a=8 pos=1 tails: 2 8
a=6 pos=1 tails: 2 6
a=3 pos=1 tails: 2 3
a=6 pos=2 tails: 2 3 6
a=9 pos=3 tails: 2 3 6 9
a=7 pos=3 tails: 2 3 6 7
LIS length = 4

ตอนเจอ 3 tails คือ 2 6 ช่องแรกที่ไม่น้อยกว่า 3 คือ 6 ที่ช่อง 1 แปลว่าลำดับยาว 2 ตอนนี้จบด้วย 3 ได้แล้ว ซึ่งดีกว่าจบด้วย 6 เลยทับ 6 ด้วย 3 พอ 6 ตัวที่สองมา ต่อจาก 3 ได้ยาว 3 ทั้งที่ถ้ายังเก็บ 6 ไว้จะต่อไม่ได้ เพราะต้องมากกว่าจริงๆ ตัวเลขแต่ละตัวทำ lower_bound หนึ่งครั้ง O(log N) ทั้งหมดจึงเป็น O(N log N) ความยาวของ tails ตอนจบคือคำตอบ

tails ไม่ใช่ LIS

ป้อน 4 กับ 3 4 5 1 ให้โปรแกรม lis-tails บรรทัดสุดท้ายของการไล่จะเป็น a=1 pos=0 tails: 1 4 5 ความยาว 3 ถูก แต่ 1 4 5 ไม่ใช่ลำดับย่อย เพราะ 1 อยู่หลัง 4 กับ 5 tails แต่ละช่องมาจากลำดับคนละชุดกัน ช่อง 0 คือลำดับ 1 ช่อง 2 คือลำดับ 3 4 5 ถ้าโจทย์ให้พิมพ์ลำดับ ห้ามพิมพ์ tails

เก็บเพิ่มสองอย่าง tail_index[k] คือ ตำแหน่ง ของตัวที่เป็นหางใน tails[k] และตอนวาง a[i] ลงช่อง pos ให้จดว่ามันต่อจากหางของช่อง pos - 1 ณ ตอนนั้น คือ previous[i] = tail_index[pos - 1] พอจบ เริ่มจากหางของช่องสุดท้ายแล้วตาม previous ย้อนกลับ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> tails, tail_index, previous(n, -1);
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(tails.begin(), tails.end(), a[i]) - tails.begin(); // (1)!
        if (pos > 0) {
            previous[i] = tail_index[pos - 1]; // (2)!
        }
        if (pos == (int)tails.size()) {
            tails.push_back(a[i]);
            tail_index.push_back(i);
        } else {
            tails[pos] = a[i];
            tail_index[pos] = i;
        }
    }
    vector<int> sequence;
    for (int i = tail_index.back(); i != -1; i = previous[i]) { // (3)!
        sequence.push_back(a[i]);
    }
    reverse(sequence.begin(), sequence.end());
    cout << sequence.size() << '\n';
    for (int k = 0; k < (int)sequence.size(); k++) {
        cout << sequence[k] << (k + 1 == (int)sequence.size() ? '\n' : ' ');
    }
    return 0;
}
  1. ส่วนนี้เหมือนโปรแกรม lis-tails ต่างกันแค่ไม่พิมพ์การไล่ และอ่านเร็วตามบทที่ 15 เพราะจะใช้กับข้อมูลล้านตัว
  2. ต้องจดตอนนี้ เพราะ tail_index[pos - 1] อาจถูกทับภายหลังด้วยตัวที่อยู่ทางขวาของ i ซึ่งต่อหน้า a[i] ไม่ได้แล้ว
  3. ได้ตัวเลขจากท้ายไปหน้า จึงต้อง reverse ก่อนพิมพ์
8
5 2 8 6 3 6 9 7

4
2 3 6 7

ได้ 2 3 6 7 ไม่ใช่ 2 3 6 9 แบบโปรแกรม O(N2) ทั้งคู่ถูก วิธีนี้ให้ลำดับที่หางของแต่ละความยาวเล็กที่สุดตอนจบ ถ้าโจทย์ระบุว่าต้องการแบบไหน ต้องคิดเงื่อนไขการเลือกเพิ่ม และทดสอบกับวิธี O(N2) ด้วยข้อมูลเล็กเสมอ

ไม่ลดลง ใช้ upper_bound

ถ้าโจทย์ยอมให้ค่าเท่ากันได้ เช่น "ลำดับย่อยที่ไม่ลดลงยาวที่สุด" ตัว x ต้องต่อท้ายลำดับที่หาง ไม่เกิน x ได้ด้วย จึงต้องหาช่องแรกที่ > x แทน คือเปลี่ยน lower_bound เป็น upper_bound คำเดียว ตามความหมายของสองฟังก์ชันในหน้า 19.2

โจทย์ต้องการตัวถัดไปต้องใช้
เพิ่มขึ้น (strictly increasing)มากกว่าตัวก่อนlower_bound
ไม่ลดลง (non-decreasing)มากกว่าหรือเท่ากับตัวก่อนupper_bound

ถ้าโจทย์ถามลำดับที่ ลดลง ไม่ต้องเขียนใหม่ ให้กลับเครื่องหมายทุกตัวเป็นค่าติดลบก่อน ลำดับที่ลดลงของค่าเดิมคือลำดับที่เพิ่มขึ้นของค่าติดลบ

เร็วขึ้นแค่ไหน

วัดบนเครื่องเดียวกับหน้า 19.1 ตัวเลขสุ่มตั้งแต่ 1 ถึง 109 วิธี O(N2) คือโปรแกรม lis-quadratic ที่ตัดส่วนพิมพ์และส่วนย้อนรอยออก เหลือแค่หาความยาว และอ่านเร็วแบบเดียวกัน วิธี O(N log N) คือโปรแกรม lis-print ทั้งโปรแกรม รวมการพิมพ์ลำดับ รันแต่ละแบบ 5 รอบ

NวิธีCode::Blocks (-Wall)-O2คำตอบ
20000O(N2)2.2 วินาที0.44 วินาที270
O(N log N)0.03 วินาที0.03 วินาที
100000O(N2)44 วินาที (5 รอบอยู่ระหว่าง 37 ถึง 50)14.5 วินาที629
O(N log N)0.04 วินาที0.04 วินาที
1000000O(N log N)0.30 วินาที0.17 วินาที1974

N เพิ่มห้าเท่าจากสองหมื่นเป็นแสน วิธี O(N2) ช้าลงราว 20 ถึง 33 เท่า ใกล้กับ 52 = 25 ที่คาดไว้ ข้อมูลแสนตัวเป็นขนาดปกติของโจทย์ TOI ถ้าเห็น N ถึงแสนแล้วโจทย์ถาม LIS ให้ใช้วิธี tails ทันที

ลองทำให้พัง

แบบที่ 1 ใช้ upper_bound กับโจทย์ที่ต้องเพิ่มขึ้นจริงๆ

นักเรียน 10 คนยืนเรียงแถว แต่ละคนมีคะแนนเต็ม 10 ครูจะเลือกคนออกมาโดยคงลำดับเดิม ให้ คนหลังได้คะแนนมากกว่าคนหน้าทุกคู่ เลือกได้มากสุดกี่คน ในโปรแกรม lis-print เปลี่ยน lower_bound เป็น upper_bound

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> tails, tail_index, previous(n, -1);
    for (int i = 0; i < n; i++) {
        int pos = upper_bound(tails.begin(), tails.end(), a[i]) - tails.begin();
        if (pos > 0) {
            previous[i] = tail_index[pos - 1];
        }
        if (pos == (int)tails.size()) {
            tails.push_back(a[i]);
            tail_index.push_back(i);
        } else {
            tails[pos] = a[i];
            tail_index[pos] = i;
        }
    }
    vector<int> sequence;
    for (int i = tail_index.back(); i != -1; i = previous[i]) {
        sequence.push_back(a[i]);
    }
    reverse(sequence.begin(), sequence.end());
    cout << sequence.size() << '\n';
    for (int k = 0; k < (int)sequence.size(); k++) {
        cout << sequence[k] << (k + 1 == (int)sequence.size() ? '\n' : ' ');
    }
    return 0;
}

10
4 4 7 2 7 7 9 3 9 10

8
4 4 7 7 7 9 9 10

ได้ 8 คน แต่ลำดับที่พิมพ์มี 4 กับ 4 ติดกัน และ 7 สามครั้ง ซึ่งผิดเงื่อนไขว่าต้องมากกว่า คำตอบที่ถูกคือ 4 ใช้ lower_bound แล้วได้ 2 3 9 10 ความผิดนี้จับยากเพราะข้อมูลที่ไม่มีค่าซ้ำเลยจะได้คำตอบเท่ากันทั้งสองแบบ ตัวอย่างในโจทย์มักไม่มีค่าซ้ำ แต่ชุดทดสอบที่ซ่อนไว้มีแน่ ทดสอบ LIS ทุกครั้งด้วยข้อมูลที่ทุกตัวเท่ากัน คำตอบแบบเพิ่มขึ้นต้องเป็น 1 แบบไม่ลดลงต้องเป็น N

ความผิดนี้เห็นในกล่องเตือนข้างบนแล้ว ความยาวของ tails ถูกเสมอ จึงผ่านโจทย์ที่ถามแค่ความยาว แต่ถ้าโจทย์ให้พิมพ์ลำดับ แล้วพิมพ์ tails จะได้ตัวเลขที่เรียงสวยแต่ไม่ใช่ลำดับย่อยจริง กับข้อมูล 3 4 5 1 ได้ 1 4 5 ต้องเก็บ tail_index กับ previous แบบโปรแกรม lis-print

สรุป

  • length[i] คือ LIS ที่จบที่ตัวที่ i ได้จาก length[j] + 1 ที่มากสุด เมื่อ j < i และ a[j] < a[i] เป็น O(N2)
  • tails[k] เก็บหางที่เล็กที่สุดของลำดับยาว k + 1 เรียงอยู่เสมอ ใช้ lower_bound หาช่องแล้วทับหรือต่อท้าย เป็น O(N log N)
  • tails ไม่ใช่ LIS ถ้าต้องพิมพ์ ให้เก็บ tail_index กับ previous แล้วย้อนกลับ
  • เพิ่มขึ้นใช้ lower_bound ไม่ลดลงใช้ upper_bound ลดลงให้กลับเครื่องหมายก่อน
  • N ถึงแสนต้องใช้ O(N log N) วิธี O(N2) ใช้ไม่ทันแม้คอมไพล์ -O2