ในข้อนี้ โจทย์ต้องการหาว่าการเปลี่ยนกล้วยไม้ให้น้อยที่สุดกี่ต้น จึงจะทำให้ความสูงของต้นกล้วยไม้ เรียงจากน้อยไปมาก

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

สังเกตต่อมาว่า การ หยิบออกให้น้อยที่สุด คือการ รักษาไว้ให้มากที่สุด โดยเราจะเปลี่ยนแนวคิดจากการหยิบออกเป็น เลือกกล้วยไม้ให้ได้จำนวนมากที่สุดที่เรียงจากน้อยไปมาก ซึ่งปัญหาดังกล่าวมีชื่อเรียกว่า Longest Nondecreasing Subsequence ซึ่งเป็น variant หนึ่งของปัญหาโด่งดังที่เรียกว่า Longest Increasing Subsequence (LIS)

ปัญหาดังกล่าวสามารถแก้ได้ในเวลา $\mathcal{O}(N^2)$ ด้วยวิธีการ Dynamic Programming โดยให้ $dp_i$ แทนจำนวนต้นกล้วยไม้ที่มากที่สุดที่สามารถรักษาไว้ได้ หากพิจารณาเฉพาะกล้วยไม้ในช่วง $1$ ถึง $i$ และหยิบต้นที่ $i$ แน่ๆแล้วด้วย

(หลังจากนี้จะใช้สัญลักษณ์ $A_i$ แทนความสูงของต้นที่ $i$ ตั้งแต่ต้นที่ $1$ ถึง $N$)

สังเกตความสัมพันธ์ของสถานะต่างๆดังนี้ $dp_i = \max_{\substack{j<i \\ A_j \leq A_i}}{dp_j+1}$ กล่าวคือ หากมั่นใจว่าจะหยิบกล้วยไม้ต้นที่ $i$ แน่ๆ เราจะต้องไปหาว่า หากหยิบต้นที่ $j$ ก่อนหน้า $i$ ที่เตี้ยกว่าหรือเท่ากับต้นที่ $i$ จะหยิบต้นไหนดีที่สุด (คือการหา max นั่นเอง) เมื่อมั่นใจว่าค่าดีสุดแล้ว เรานำามาบวก 1 เพื่อคิดค่าต้นปัจจุบันไปด้วย ก็จะได้ $dp_i$ สำเร็จ

ตัวอย่างโค้ด

int dp[1000005];
int A[1000005]; // Height of i-th orchid
for (int i = 1; i <= N; i++) {
  int opt = 0; // In case there is no predecessor
  for (int j = 1; j < i; j++) {
    if (A[j] <= A[i]) {
      opt = max(opt, dp[j]); // Update optimal value
    }
  }
  dp[i] = opt + 1;
}

ต่อมาเราสังเกตว่าเวลา $\mathcal{O}(N^2)$ นั้นยังไม่เร็วพอ และมีวิธีการ optimize ให้ดียิ่งขึ้น โดยการทำ Longest Nondecreasing Subsequence ใน $\mathcal{O}(N \log N)$ โดยเปลี่ยนวิธีการเก็บ $dp$ ดังนี้

เราจะค่อยๆพิจารณาเริ่มจากอาเรย์ว่างเปล่า แล้วค่อยๆใส่เพิ่มตัวท้ายไปเรื่อยๆจนครบทั้ง $N$ ตัว

สมมติว่าแต่ละ $i$ ในกาลเวลาใดๆ เมื่อเราสมมติว่า Longest Nondecreasing Subsequence จะยาว $i$ แน่ๆ ลองพิจารณาทุก subsequence ที่เป็นไปได้ตามเงื่อนไขดังกล่าว สังเกตว่าเราต้องการให้ตัวสุดท้ายมีค่า น้อยที่สุดเท่าที่จะเป็นไปได้ เพราะหากมีค่าน้อยเท่าไหร่ ก็ยิ่งสามารถมีโอกาสนำไปใช้ต่อได้มากเท่านั้น

ตัวอย่างเช่น 1 5 2 3 หากพิจารณา Longest Nondecreasing Subsequence ความยาว $2$ แล้ว จะได้ว่ามีได้ทั้งหมด ดังนี้ 1 5, 1 2, 1 3, 2 3 สังเกตว่าข้อมูลที่มีผลมีเพียงตัวสุดท้ายเท่านั้น (นั่นคือ 5, 2, 3, 3 ตามลำดับ) หากต้องการเติม 6 ต่อท้าย เราสามารถเติมใน subsequence ไหนก็ได้ แต่หากต้องการเติม 2 เราจะไม่สามารถเติมหลัง subsequence ที่จบด้วย 3 หรือ 5 ได้เลย เพราะจะทำให้มันไม่เรียงจากน้อยไปมาก

เพื่อให้มองเห็นง่าย เราจะเก็บ $L_i$ แทนว่า หาก Longest Nondecreasing Subsequence ยาว $i$ แล้ว ตัวสุดท้ายของเหล่า subsequence ทุกแบบที่เป็นไปได้ที่ยาว $i$ นั้น จะมีค่า น้อยที่สุดเท่าที่จะเป็นไปได้ เท่าใด

พิจารณาตัวอย่าง 1 2 6 9 7 4 5 3

ในขณะแรก $L$ จะยังคงว่างเปล่า

ต่อมาเมื่อพิจารณา 1 จะได้

$L$ = [1]

ต่อมาเมื่อพิจารณา 2 จะได้

$L$ = [1, 2]

ต่อมาเมื่อพิจารณา 6 จะได้

$L$ = [1, 2, 6]

ต่อมาเมื่อพิจารณา 9 จะได้

$L$ = [1, 2, 6, 9]

ต่อมาเมื่อพิจารณา 7 จะได้

$L$ = [1, 2, 6, 7]

ต่อมาเมื่อพิจารณา 4 จะได้

$L$ = [1, 2, 4, 7]

ต่อมาเมื่อพิจารณา 5 จะได้

$L$ = [1, 2, 4, 5]

ต่อมาเมื่อพิจารณา 3 จะได้

$L$ = [1, 2, 3, 5]

ผลสุดท้ายแล้ว คำตอบ จำนวนต้นกล้วยไม้ที่มากที่สุดที่สามารถรักษาไว้ได้ ก็คือขนาดของ $L$ นั่นเอง

คำถามต่อมาคือ หากทำวิธีนี้แล้ว จะต้องรักษาสภาพ $L$ ในแต่ละช่วงเวลาอย่างไร ซึ่งวิธีการอย่างง่ายคือ สังเกตว่า หากมี $L$ เดิมคงอยู่แล้ว แล้วมีการเติม $x$ มาพิจารณา แล้ว จะมีผลอย่างไรต่อ $L$ สังเกตว่า หากเป็นไปได้เราก็อยากให้ $L$ ยาวขึ้นอยู่แล้ว นั่นคือ หาก $x$ มากกว่าหรือเท่ากับตัวสุดท้ายของ $L$ เราจะเติม $x$ ต่อท้าย $L$ ไป แต่หากไม่เป็นเช่นนั้น เราจะดูว่า $x$ จะไปช่วยลดค่า $L_i$ บางอันได้หรือเปล่า เพื่อให้สามารถใช้ค่าปัจจุบันเพิ่มโอกาสไปต่อกับค่าในอนาคตได้ สังเกตว่า $x$ จะสามารถนำไปต่อท้าย $L_i$ เฉพาะที่มีค่าน้อยกว่าหรือเท่ากับ $x$ เท่านั้น และสังเกตว่า $L$ จะเรียงจากน้อยไปมากเสมอ แสดงว่าหาก $x$ น้อยกว่าค่าสูงสุดใน $L$ จะต้องมี $i$ ที่ $L_i > x$ และ ($i = 1$ หรือ $L_{i-1} \leq x$) ที่เราสามารถนำ $x$ ไปต่อหลังจาก $L_{i-1}$ ได้ (หรือใช้ $x$ เป็นตัวแรกหาก $i = 1$) เราสามารถทำการแทนที่ $L_{i}$ ด้วย $x$ ได้เลย เพื่อทำให้ $L$ นั้น optimal (ลองสังเกตตัวอย่างในแต่ละขั้น จะเห็นภาพได้ชัดเจนยิ่งขึ้น)

ตัวอย่างโค้ด

int L[1000005];
int A[1000005]; // Height of i-th orchid
int size = 0;
for (int t = 1; t <= N; t++) {
  int x = A[t];
  if (x >= L[size]) { // In case we can add x to the end of L.
    L[size + 1] = x;
    size++;
  } else {
    for (int i = 1; i <= size; i++) {
      if (L[i] > x && (i == 1 || L[i - 1] <= x)) {
        L[i] = x;
        break;
      }
    }
  }
}

ซึ่งเราจะเห็นได้ว่า โค้ดข้างต้นก็ยังใช้เวลา $\mathcal{O}(N^2)$ อยู่

ต่อมาเราสามารถทำให้เร็วขึ้นได้โดยอาศัยหลักการที่ว่า $L$ นั้นเรียงจากน้อยไปมาก โดยเราสามารถทำการ Binary Search ใน $\mathcal{O}(\log N)$ เพื่อหาตำแหน่ง $i$ ในเวลาใดๆ ดังนี้

int L[1000005];
int A[1000005]; // Height of i-th orchid
int size = 0;
for (int t = 1; t <= N; t++) {
  int x = A[t];
  if (x >= L[size]) { // In case we can add x to the end of L.
    L[size + 1] = x;
    size++;
  } else {
    int lo = 1;
    int hi = size;
    int mid;
    while (lo < hi) {
      mid = (lo + hi) / 2;
      if (x > L[mid])
        hi = mid;
      else
        lo = mid + 1;
    }
    L[mid] = x;
  }
}

เท่านี้ อัลกอริทึมดังกล่าวก็จะสามารถทำงานในเวลา $\mathcal{O}(N \log N)$ ได้แล้ว (หรือเพื่อความแม่นยำ สามารถเรียกได้ว่าทำงานในเวลา $\mathcal{O}(N \log |L|)$) เมื่อ $|L|$ แทนขนาดของ Longest Nondecreasing Subsequence

นอกจากนี้ เพื่อความง่าย จึงมีแนวทางการเขียนยอดนิยมสำหรับการแก้โจทย์ข้อนี้ ดังนี้

vector<int> L;
int A[1000005];
for (int t = 1; t <= N; t++) {
  int x = A[t];
  auto it = upper_bound(L.begin(), L.end(), x);
  if (it == L.end())
    L.push_back(x);
  else
    *it = x;
}

โดยฟังก์ชัน upper_bound(L.begin(), L.end(), x) จะทำการหาว่า $i$ ที่น้อยที่สุดที่ $L_i > x$ เป็นเท่าใด และคืนค่าเป็น random access iterator ชี้ตำแหน่งนั้น โดย assume ว่า $L$ นั้นเรียงจากน้อยไปมากแล้ว ต่อมาเราตรวจสอบว่า $i$ ดังกล่าวนั้น พ้นขอบเขตของ $L$ หรือไม่ หากพ้นไปแล้วถือว่าสามารถนำ $x$ ต่อท้าย $L$ ได้ แต่หากอยู่ภายใน $L$ จะสามารถปรับลดค่าดังกล่าวลงมาได้เลย