ดูต้นฉบับสำหรับ 418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 5

== ข้อย่อย 1 ==
อินพุต: ลำดับของจำนวนเต็มที่มีความยาว <math> n \,</math>

เอาพุต: ลำดับย่อยของลำดับที่เป็นอินพุตที่มีความยาวมากที่สุด และเป็นลำดับเลขคณิต

แนวคิด ข้อนี้วัตถุที่เราต้องการหาคือลำดับย่อย ตำแหน่งเริ่มต้น <math>i \,</math>และตำแหน่งสุดท้าย <math>j \,</math>ในลำดับที่ให้มา โดยที่ <math>i \leq j \,</math>หรือคือช่วงที่เราเรียนกันไปแล้วในห้องเรียนนั่นเอง และเงื่อนไข คือต้องเป็นลำดับเลขคณิต(ที่มีความยาวมากที่สุด) ดังนั้นสิ่งที่อัลกอริทึมของเราต้องทำ คือหยิบช่วงแต่ละช่วง (ลำดับย่อยแต่ละลำดับ) มาดู แล้วดูว่ามันเป็นลำดับเลขคณิตหรือไม่ ถ้าใช่ก็ตรวจสอบอีกว่า มันเป็นลำดับเลขคณิตที่เราเคยรู้จักและยาวกว่าหรือไม่ ถ้ายาวกว่าก็เปลี่ยนมาจำลำดับย่อยใหม่นี้

จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c">
ABS(x,y) // เป็น subroutine ที่ใช้ในการหาผลต่างระหว่างเลขสองตัว
{
    if (x-y < 0)
        return ((-1).(x-y))
    return(x-y)
}
</geshi>

<geshi lang="c">
CHECK_ARITH(A,i,j) // เป็น subroutine ที่ใช้ในการตรวจสอบว่าลำดับย่อยในช่วง i ถึง j เป็นลำดับเลขคณิตหรือไม่

{
     k = ABS(A[i],A[i+1]) // กำหนดค่า k เป็นผลต่างระหว่างเลขตัวแรกกับตัวที่สองในลำดับย่อย
         for k=i+1 to k<j
     {
         if(ABS(A[k],A[k+1] != k)) // ถ้ามีตัวเลขของตัวในลำดับย่อยมีผลต่างไม่เท่ากับ k ก็บอกว่าลำดับย่อยในช่วง i ถึง j นี้ไม่เป็นลำดับเลขคณิต
                          retrun (0)
         else
             return(1)
     }
}
</geshi>

<geshi lang="c">
LONGESTINTERVAL(A,n,maxi,maxj)
{
     max = -10000000
     for i=o to i=n
     {
          for j=i to j = n 
          {
               flag=CHECK_ARITH(A,i,j) // ตรวจสอบว่าลำดับย่อยที่กำลังพิจารณาเป็นลำดับเลขคณิตหรือไม่
                              if (flag) // ถ้าเป็นลำดับเลขคณิต
                              {
                    if ((j-i+1)> max) // ตรวจสอบดูว่าความยาวของลำดับเลขคณิตนี้ยาวกว่าลำดับเลขคณิตก่อนหน้าที่เคยเจอหรือไม่
                                   maxi = i  // ถ้าใช่ก็เปลี่ยนไปจำลำดับเลขคณิตที่ยาวกว่าลำดับก่อนหน้านี้
                                  maxj = j
               } // end if flag
           } // end for j
      } // end for i
} // end pseudocode
</geshi>

== ข้อย่อย 2 ==
โจทย์ต้องการให้อัลกอริทึมทำงานได้ในเวลา<math>O(n) \,</math> นั่นคือ พออ่านอินพุตเสร็จแล้วต้องทำการตรวจสอบได้ด้วยว่าเป็นลำดับเลขคณิตหรือไม่ พร้อมทั้งต้องหาช่วง(ลำดับย่อย)ที่เป็นลำดับเลขคณิตที่ยาวที่สุดได้ด้วย ซึ่งการทำงานดังกล่าวจะทำได้ เมื่อเราทำการคำนวณผลต่างระหว่างสมาชิกในลำดับไปพร้อม ๆ กับการหยิบสมาชิกแต่ละตัวมาดูนั่นเอง นั่นคือ เมื่อเราพิจารณาสมาชิกตัวที่หนึ่ง เราก็หาผลต่างของมันกับสมาชิกตัวที่สอง เมื่อพิจารณาสมาชิกตัวที่สอง เราก็หาผลต่างของมันกับสมาชิกตัวที่สาม ทำแบบนี้ไปเรื่อย ๆ เมื่อพิจารณาครบทุกตัว ตอนนี้เราก็จะมีผลต่างระหว่างสมาชิกทุกตัวในลำดับอินพุตแล้ว จากนั้นวิธีการตรวจสอบว่าเป็นลำดับเลขคณิตที่ยาวที่สุดหรือไม่ก็ทำได้โดยดูว่าค่าผลต่างพวกนี้เปลี่ยนหรือไม่ ถ้ายังไม่เปลี่ยนก็นับว่าเป็นลำดับเลขคณิตไปเรื่อย ๆ แต่ถ้าเปลี่ยนก็แสดงว่าไม่เป็นลำดับเลขคณิตแล้ว ตัวแปรที่ใช้ในการจำว่าตำแหน่งเริ่มของลำดับย่อยก็ต้องเปลี่ยนไป แล้วเริ่มนับความยาวใหม่นั่นเอง

จากแนวคิดข้างต้นสามารถ เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c">
GENERATE(A,D,n,maxi,maxj)
{
     l = 0, count = 0
     for k=0 to k<n // ทำการหาค่าผลต่างของสมาชิกในลำดับย่อยเก็บไว้ในอะเรย์ D
     {
          D[l] = ABS(A[k],A[k+1])
          l <-- l + 1
     }
     for k=0 to k<n
     {       
          if (D[k] = D[k+1]) // ถ้าผลต่างของ A[k] กับ A[k+1] เท่ากับผลต่างของ A[k+1] กับ A[k+2]
          {
               count = count + 1
               maxi = k
               maxj = k+2
          } 
          count = 0
      }
}
</geshi>