ขนาดเซิร์ฟอาร์เรย์สูงสุดที่ตรงตามเงื่อนไขที่กำหนดในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม n ตัว ภารกิจของเราคือสร้างโปรแกรมเพื่อหาขนาดเซิร์ฟอาร์เรย์สูงสุดที่ตรงตามเงื่อนไขที่กำหนด

คำอธิบายปัญหา

เราต้องหาความยาวของเซิร์ฟอาร์เรย์ที่ใหญ่ที่สุดที่ตรงตามเงื่อนไขใดเงื่อนไขหนึ่งด้านล่าง

• arr[k] > arr[k+1] ถ้า k เป็นคี่ และ arr[k] < arr[k+1] ถ้า k เป็นคู่ สำหรับทุกองค์ประกอบของเซิร์ฟอาร์เรย์
• arr[k] < arr[k+1] ถ้า k เป็นคี่ และ arr[k] > arr[k+1] ถ้า k เป็นคู่ สำหรับทุกองค์ประกอบของเซิร์ฟอาร์เรย์

ที่นี่ k คือดัชนีขององค์ประกอบของเซิร์ฟอาร์เรย์ใน arr[]

ตัวอย่าง

อินพุต

arr[] = {7, 3, 1, 5, 4, 2, 9}

เอาต์พุต

4

คำอธิบาย

เซิร์ฟอาร์เรย์ {3, 1, 5, 4} ตรงตามเงื่อนไข 1
k = 1(คี่), arr[k] > arr[k+1], 3 > 1
k = 2(คู่), arr[k] < arr[k+1], 1 < 5
k = 3(คี่), arr[k] > arr[k+1], 5 > 4

แนวทางแก้ปัญหา

เราสามารถเห็นได้จากตัวอย่างที่ว่า สำหรับเงื่อนไขใดๆ ที่จะเป็นจริง เซิร์ฟอาร์เรย์ควรจะมีองค์ประกอบมากกว่า-น้อยกว่าสลับกัน คือ ถ้า 1st > 2nd แล้ว 2nd < 3rd และต่อไป

ตอนนี้ เพื่อความสะดวกในการคำนวณ เราจะสร้างอาร์เรย์ความสัมพันธ์ (relation array) ที่บ่งบอกความสัมพันธ์นี้ ดังต่อไปนี้คือวิธีที่เราจะปรับแต่งอาร์เรย์ความสัมพันธ์

ถ้า arr[i] == arr[i + 1], relArr[i] = 'E' 
ถ้า arr[i] > arr[i + 1], relArr[i] = 'G' 
ถ้า arr[i] < arr[i + 1], relArr[i] = 'S'

โดยใช้อาร์เรย์นี้ เราสามารถหาขนาดเซิร์ฟอาร์เรย์สูงสุดได้ง่าย เซิร์ฟอาร์เรย์ที่จะพิจารณาจะมี 'G' และ 'S' สลับกัน

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

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#include <iostream> 
using namespace std; 

char findRel(int a, int b) { 
    if(a > b) 
        return 'G'; 
    else if(a < b) 
        return 'S'; 
    return 'E'; 
} 

int calcMaxSubArray(int arr[], int n) { 
    int maxLen = 1; 
    int len = 1; 
    char c = findRel(arr[0], arr[1]); 
    for(int i = 1; i <= n-1; i++){ 
        if(c == 'S' && findRel(arr[i], arr[i + 1]) == 'G') 
            len++; 
        else if(c == 'G' && findRel(arr[i], arr[i + 1]) == 'S') 
            len++; 
        else { 
            if(maxLen < (len + 1)) 
                maxLen = (len + 1); 
            len = 1; 
        } 
        c = findRel(arr[i], arr[i+1]); 
    } 
    return maxLen; 
} 

int main() { 
    int arr[] = {7, 3, 1, 5, 4, 2, 9}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "The maximum size of sub-array that satisfies the given condition is " << calcMaxSubArray(arr, n); 
}

เอาต์พุต

The maximum size of sub-array that satisfies the given condition is 4