ผลที่ตามมาของ Bitonic ที่ยาวที่สุด


ระดับความยาก ยาก
ถามบ่อยใน CodeNation เดอชอว์ Google มอร์แกน JP ไมโครซอฟท์
แถว การเขียนโปรแกรมแบบไดนามิก

สมมติว่าคุณมีไฟล์ แถว of จำนวนเต็ม คำชี้แจงปัญหาขอให้ค้นหาบิตโทนิกที่ต่อมาที่ยาวที่สุด ลำดับบิตโทนิคของอาร์เรย์ถือเป็นลำดับที่เพิ่มขึ้นก่อนแล้วจึงลดลง

ตัวอย่าง

arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7

คำอธิบาย

1 4 76 78 54 32 23 (เพิ่มครั้งแรกสูงสุด 78 แล้วลดลงจนถึง 23

ผลที่ตามมาของ Bitonic ที่ยาวที่สุด

 

ขั้นตอนวิธี

  1. ประกาศอาร์เรย์ IncreSeq [] มีขนาดเท่ากับความยาวของความยาวอาร์เรย์ที่กำหนด
  2. เริ่มต้นองค์ประกอบดัชนีทั้งหมดเป็น 1 ของอาร์เรย์ที่สร้างขึ้น IncreSeq []
  3. ค้นหาลำดับต่อมาที่เพิ่มขึ้นยาวนานที่สุดโดยเก็บไว้ใน IncreSeq [] จากซ้ายไปขวา
  4. ประกาศอาร์เรย์ ลดลง Seq [] มีขนาดเท่ากับความยาวของอาร์เรย์ที่กำหนด
  5. ค้นหาลำดับการลดลงที่ยาวที่สุดในการข้ามจากขวาไปซ้ายและโดยการจัดเก็บไว้ในการลดลง Seq []
  6. เริ่มต้นตัวแปรที่เรียกว่า maxOutput เป็น IncreasedSeq [0] + lessasingSeq [0] - 1
  7. หาค่าสูงสุดของ IncreaseSeq [i] + ลดลง Seq [i] - 1 และจัดเก็บไว้ที่ maxOutput
  8. ส่งคืน maxOutput.

คำอธิบาย

อาร์เรย์อินพุตของขนาด n ประกอบด้วยจำนวนเต็มบวก เราถูกขอให้ค้นหาลำดับบิตโทนิคที่ยาวที่สุดของอาร์เรย์ที่กำหนด ลำดับบิตโทนิกสามารถกำหนดให้เป็นลำดับที่เพิ่มขึ้นก่อนซึ่งหมายถึงจำนวนในลำดับแรกจะเพิ่มขึ้น จากนั้นจำนวนจะลดลงจนจบลำดับ เราจำเป็นต้องกำหนดความยาวของลำดับบิตโทนิคที่ยาวที่สุด

ขั้นแรกให้แยกโซลูชันออกเป็นสองส่วน เราประกาศสองอาร์เรย์อาร์เรย์แรกถือเป็น เพิ่มขึ้น อาร์เรย์ ลำดับการเพิ่มที่ยาวที่สุดคือลำดับที่ตัวเลขควรอยู่ในลำดับที่เพิ่มขึ้นเป็นลำดับแรก ดังนั้นเราจะสำรวจอาร์เรย์ในลูปที่ซ้อนกัน ค้นหาสิ่งต่อมาที่เพิ่มมากขึ้น จากนั้นเราต้องตรวจสอบเงื่อนไขว่าหากองค์ประกอบปัจจุบันน้อยกว่าองค์ประกอบถัดไป และองค์ประกอบปัจจุบันของ IncreSeq น้อยกว่าองค์ประกอบถัดไปของ IncreSeq [] ถ้าเป็นจริงให้เก็บองค์ประกอบเป็น IncreSeq [j] + 1 สิ่งนี้จะเพิ่มขึ้นเนื่องจากเราได้เตรียมข้อมูลเบื้องต้นให้อาร์เรย์เป็น 1 ในนั้นแล้ว

ประการที่สองประกาศอาร์เรย์ ลดลง Seq [] ในการลดลงนี้เราจะสำรวจอาร์เรย์ในรูปแบบการวนซ้ำที่ซ้อนกันจากขวาไปซ้ายของอาร์เรย์ เราจะตรวจสอบว่าองค์ประกอบปัจจุบันมากกว่าองค์ประกอบถัดไปหรือไม่ เพราะเรากำลังลัดเลาะจากขวาไปซ้าย จากนั้นอัปเดตไปยังค่าลดลง Seq [i] เป็นลดลง Seq [j] +1 ในขั้นตอนสุดท้ายของโค้ดเราต้องหาค่า maximumSeq [i] + reductionSeq [i] - 1 ซึ่งเก็บไว้ใน maxOutput

รหัส

รหัส C ++ สำหรับผลที่ตามมาของ Bitonic ที่ยาวที่สุด

#include<iostream>

using namespace std;

int BitonicSequence( int arr[], int n )
{
    int i, j;

    int *increasingSeq = new int[n];
    for (i = 0; i < n; i++)
        increasingSeq[i] = 1;

    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                increasingSeq[i] = increasingSeq[j] + 1;

    int *decreasingSeq = new int [n];
    for (i = 0; i < n; i++)
        decreasingSeq[i] = 1;

    for (i = n-2; i >= 0; i--)
        for (j = n-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                decreasingSeq[i] = decreasingSeq[j] + 1;

    int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

    for (i = 1; i < n; i++)
        if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
            maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

    return maxOutput;

}
int main()
{
    int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
    return 0;
}
Length of Longest Bitonic Sequence is 7

รหัส Java สำหรับผลที่ตามมาของ Bitonic ที่ยาวที่สุด

class longestBitonicSequence
{
    public static int BitonicSequence( int arr[], int n )
    {
        int i, j;

        int[] increasingSeq = new int[n];
        for (i = 0; i < n; i++)
            increasingSeq[i] = 1;

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                    increasingSeq[i] = increasingSeq[j] + 1;

        int[] decreasingSeq = new int [n];
        for (i = 0; i < n; i++)
            decreasingSeq[i] = 1;

        for (i = n-2; i >= 0; i--)
            for (j = n-1; j > i; j--)
                if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                    decreasingSeq[i] = decreasingSeq[j] + 1;


        int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

        for (i = 1; i < n; i++)
            if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
                maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

        return maxOutput;
    }

    public static void main (String[] args)
    {
        int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
        int n = arr.length;
        System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
    }
}
Length of longest bitonic sequence is 7

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

บน2ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราใช้ลูปซ้อนกันซึ่งทำให้อัลกอริทึมทำงานในเวลาพหุนาม

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราใช้อาร์เรย์พิเศษสองอาร์เรย์ที่มีขนาดขึ้นอยู่กับอาร์เรย์อินพุต ความซับซ้อนของพื้นที่เป็นเชิงเส้น