ข้อนี้กำหนดให้มีต้นไม้ $N$ ต้น โดยต้นที่ $i$ สูง $H_i$ และจะเลือกตัดต้นไหนทิ้งก็ได้

ต้นที่ $j$ จะเห็นได้หากทุกต้น $i$ ที่ $i < j$ ที่ไม่โดนตัดมี $H_i < H_j$ (ไม่โดนบัง)

โจทย์นี้ถามว่าหากเลือกตัดดีที่สุดจะเห็นได้มากสุดกี่ต้น

แนวคิด

ข้อนี้เป็นโจทย์ Longest Increasing Subsequence (LIS) โดยตรงเพราะสามารถตัดทุกต้นที่อยู่นอก LIS ให้เหลือ LIS ที่เป็นต้นไม้ที่จะมองเห็นทั้งหมด

Longest Increasing Subsequence

Longest Increasing Subsequence (ปัญหาลำดับย่อยเพิ่มยาวที่สุด) เป็นปัญหาที่ถามว่าหากมี Array $H_1, H_2, \dots, H_N$ จะสามารถเลือก Subsequence (ลำดับย่อย) $H_{a_1}, H_{a_2}, \dots, H_{a_c}$ โดยที่ $a_1 < a_2< \dots < a_c$ และ $H_{a_1} < H_{a_2}< \dots < H_{a_c}$ ที่ยาวสุดได้เท่าไหร่

สำหรับวิธีการหา Longest Increasing Subsequence จะสามารถใช้ Dynamic Programming โดยจะทำเป็นขั้นๆ หนึ่งขั้นสำหรับทุกค่า $H_i$ โดยเก็บค่า $DP[c]$ ที่แทนว่าหากเลือก Subsequence ใน $H_1, H_2, \dots, H_i$ ที่มีความยาว $c$ จะสามารถจบได้ด้วยค่าสุดท้ายต่ำสุดเท่าไหร่

สังเกตว่า $DP[0], DP[1] , \dots, DP[N]$ ควรเป็นลำดับไม่ลด $(DP[0] \leq DP[1] \leq \dots \leq DP[N])$ เพราะหากมีลำดับยาว $c$ ที่จบด้วยค่า $DP[c]$ จะเลือกตัดตัวสุดท้ายจากลำดับที่ได้ค่า $DP[c]$ ออกจะทำให้เหลือลำดับยาว $c-1$ ที่จบด้วยค่า $DP[c-1] < DP[c]$

ในตอนเริ่มจะมี $DP[c] = \infty$ สำหรับ $c\geq 1$ และ $DP[0]=-\infty$ แทน Subsequence ว่างที่มีความยาว $0$ และจบด้วยค่าต่ำสุด $-\infty$ เพราะจะเอาค่าอะไรมาต่อก็ได้โดยที่ Subsequence ที่ได้ยังเป็นลำดับที่เพิ่มอยู่

สมมิตว่า $DP[0], DP[1] , \dots, DP[N]$ เป็นลำดับไม่ลด สำหรับแต่ละ $i$ จะต้องหา $DP[x]$ ที่มี $x$ มากสุดที่ $DP[x] <H_i$ และตั้งค่า $DP[x+1] = \min (DP[x+1], H_i)$ เพราะค่า $H_i$ สามารถเอามาต่อลำดับย่อยความยาว $x$ ที่จบที่ $DP[x]$ ที่ $DP[x]< H_i$ เพื่อให้ได้ลำดับย่อยเพิ่มยาว $x+1$ ที่จบด้วยค่า $H_i$ ในขั้นตอนนี้สังเกตว่า $DP[0], DP[1] , \dots, DP[N]$ จะคงสถานะเป็นลำดับไม่ลดหลังการแก้ค่า เพราะ $H_i$ ซึ่งอาจมาแทน $DP[x+1]$ จะมากกว่า $DP[x]$ และน้อยกว่า $DP[x+2]$ ในทุกครั้ง

สังเกตว่าเราไม่สามารถลดค่า $DP[a]$ สำหรับ $a < x$ เพราะ $H_i$ จะมากกว่าค่าเหล่านั้น และไม่สามารถนำ $H_i$ ไปต่อลำดับที่ยาวกว่า $x$ เพราะ $DP[a] > H_i$ สำหรับ $a > x$ (ถ้าเอาไปต่อจะไม่เป็นลำดับย่อยเพิ่ม) ดังนั้นการพิจารณาเพียง $DP[x]$ เพื่อแก้ค่า $DP[x+1]$ นั้นถูกต้องแล้ว

คุณสมบัติไม่ลดของ $DP[0], DP[1] , \dots, DP[N]$ ทำให้เราสามารถใช้ Binary Search ในการหาค่า $x$ ดังกล่าวที่เป็นค่าที่มากสุดที่ $DP[x] < H_i$ ซึ่งใช้เวลา $\mathcal{O}(\log N)$ ในแต่ละครั้ง ทั้งขั้นตอนวิธีจึงใช้เวลา $\mathcal{O}(N \log N)$

คำตอบจะเป็นค่า $x+1$ มากที่สุดที่ได้จากแต่ละขั้น

ตัวอย่างโค้ดประกอบคำอธิบาย

  for (int i = 1; i <= n; i++)
    DP[i] = 1000000000;

  int ans = -1000000000;
  for (int i = 1; i <= n; i++) {
    int b = 0, e = n, x = 0;
    while (b <= e) {
      int mid = (b + e) / 2;
      if (DP[mid] < H[i]) {
        x = max(x, mid);
        b = mid + 1;
      } else
        e = mid - 1;
    }

    DP[x + 1] = min(DP[x + 1], H[i]);
    ans = max(ans, x + 1);
  }