IMOS Method I : หนึ่งมิติ - de algorismo

IMOS Method* : เป็นการต่อยอดเทคนิกการบวกสะสม**
เพื่อใช้กับมิติที่สูงขึ้นและจำนวนลำดับที่มากขึ้น

IMOS Method แบบพื้นฐานที่สุดคือการบวกในหนึ่งอาเรย์มิติ
รูปที่ ๑ แสดงการเพิ่มค่าข้อมูลลงในอาเรย์หนึ่งมิติ
ปัญหา คุณเปิดร้านกาแฟ สำหรับทุกลูกค้า i เข้าร้านในเวลา Si และออกในเวลา Ei (0 ≤ Si <Ei ≤ T)
ให้ค่า M คือจำนวนที่ลูกค้าอยู่ในร้าน ณ เวลาหนึ่ง ๆ จงหาค่า M ที่มากที่สุด

วิธีแก้ปัญหาที่บ้านนอกที่สุด คือการไล่บวกแม่งทุกตัว (C แทนจำนวนลูกค้า และ T แทนเวลาทำการ) อัลกอฯนี้มี O(CT) ซึ่งแน่นอนว่าโจทย์ให้ C กับ T มาล้านเศษแน่นอน รับประกันว่าวิธีนี้จะติด T รัว ๆ
```
for (int i = 0; i < T; i++) 
  table[i] = 0;
for (int i = 0; i < C; i++) {
  // Read note 1
  for (int j = S[i]; j < E[i]; j++) {
    table[j]++;
  }
}
// Read note 2
M = 0;
for (int i = 0; i < T; i++) {
  if (M < table[i]) M = table[i];
}
```
Note 1: ไล่บวกจำนวนลูกค้าในช่วงเวลาที่ลูกค้าอยู่ไปทีละคน
Note 2: หาจำนวนลูกค้าที่มากที่สุดจากทุกช่วงเวลา

แต่ถ้าใช้ IMOS อัลกอฯนี้จะเหลือ O(C+T) เท่านั้น วิธีการคือบวกจำนวนลูกค้าในช่วงเวลาที่ลูกค้าเข้ามาและลบจำนวนลูกค้าออกในเวลาที่ลูกค้าออกจากร้านเท่านั้น เช่น
มีลูกค้า C1 {S = 1, E = 3}, C2 {2, 4}, C3 {3, 4} จะได้ว่าในเวลา 1<=T<=4 จะมีจำนวนลูกค้าดังนี้
+ C1 : 1, 0, -1, 0
+ C2 : 1, 1, -1, -1
+ C3 : 1, 1, 0, -2
จากนั้น เกลี่ย จำนวนของลูกค้าด้วยวิธีเดียวกับ Quick Sum คือ N(Tn) += N(Tn-1) | n > 0 จึงเป็น
1, 2, 2, 0
ซึ่งถ้าใช้วิธีแรกก็จะได้คำตอบเดียวกันในช่วง [S, E)

for (int i = 0; i < T; i++)
table[i] = 0;
for (int i = 0; i < C; i++) {
table[S[i]]++; // Read note 1
table[E[i]]--; // Read note 2
}
// Read note 3
for (int i = 1; i < T; i++)
table[i] += table[i - 1];

// Read note 4
M = 0;
for (int i = 0; i < T; i++)
if (M < table[i]) M = table[i];
Note 1: บวกจำนวนลูกค้าในเวลาที่มีลูกค้าเข้ามา ไม่บวกไล่ไปเหมือนวิธีแรก
Note 2: ลบจำนวนลูกค้าเมื่อลูกค้าออก
Note 3: เกลี่ย จำนวนลูกค้าในทุกช่วงเวลา
Note 4: หาจำนวนลูกค้าที่มากที่สุดจากทุกช่วงเวลา
ติดตามต่อ EP. II มิติที่สูงขึ้น
* (จากคำว่า いもす法; เอาตรง ๆ คือไม่รู้จะแปลชื่อมันว่าอะไร)
**(รู้จักในชื่อ Quick Sum)
อ้างอิงจาก https://imoz.jp/algorithms/imos_method.html
ได้รับอนุญาติให้เผยแพร่เป็นภาษาไทยจาก @imos เจ้าของเว็บไซต์อ้างอิง

IMOS Method* : เป็นการต่อยอดเทคนิกการบวกสะสม**
เพื่อใช้กับมิติที่สูงขึ้นและจำนวนลำดับที่มากขึ้น

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

IMOS Method* : เป็นการต่อยอดเทคนิกการบวกสะสม**เพื่อใช้กับมิติที่สูงขึ้นและจำนวนลำดับที่มากขึ้น

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

IMOS Method* : เป็นการต่อยอดเทคนิกการบวกสะสม**
เพื่อใช้กับมิติที่สูงขึ้นและจำนวนลำดับที่มากขึ้น