បនា្ទាប់ប៊ីខនវែងបំផុត  


កម្រិតលំបាក រឹង
សួរញឹកញាប់ លេខកូដ ឌីសៅ ក្រុមហ៊ុន google ដោយឡែកក្រុមហ៊ុន JP Morgan ក្រុមហ៊ុន Microsoft
អារេ ការសរសេរកម្មវិធីឌីណាមិក

ឧបមាថាអ្នកមាន អារេ of ចំនួនគត់, សេចក្តីថ្លែងការណ៍បញ្ហាសួរដើម្បីរកឱ្យឃើញនូវបណ្តុំហ្គោដវែងបំផុត។ លំដាប់តំរុយនៃអារេត្រូវបានគេចាត់ទុកថាជាលំដាប់ដែលកើនឡើងដំបូងហើយបន្ទាប់មកថយចុះ។

ឧទាហរណ៍  

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

ការពន្យល់

1 4 76 78 54 32 23 (បង្កើនលើកដំបូងរហូតដល់ ៧៨ ហើយបន្ទាប់មកថយចុះរហូតដល់ ២៣ ។

បនា្ទាប់ប៊ីខនវែងបំផុតពិន

 

ក្បួនដោះស្រាយ  

  1. ប្រកាសអារេមួយ ការកើនឡើង Sq នៃទំហំដូចគ្នានឹងប្រវែងនៃប្រវែងអារេដែលបានផ្តល់ឱ្យ។
  2. ចាប់ផ្តើមធាតុចង្អុលបង្ហាញទាំងអស់ជាធាតុ ១ នៃអារេដែលបានបង្កើតកំពុងកើនឡើង [] ។
  3. ស្វែងយល់ពីការបន្តកើនឡើងវែងបំផុតដោយទុកវានៅក្នុងអេសអេសអេពីកើនពីឆ្វេងទៅស្តាំ។
  4. ប្រកាសអារេមួយ ថយចុះអេស។ នៃទំហំដូចគ្នានឹងប្រវែងនៃអារេដែលបានផ្តល់ឱ្យ។
  5. រកឃើញការថយចុះបន្ទាប់វែងបំផុតឆ្លងកាត់ពីស្តាំទៅឆ្វេងនិងដោយរក្សាទុកវាទៅក្នុងសូអេសថយចុះ។
  6. ចាប់ផ្តើមអថេរដែលហៅថា maxOutput ដើម្បីបង្កើន Seq [0] + បន្ថយ Seq [0] - ១ ។
  7. ស្វែងយល់ពីចំនួនអតិបរមា ការកើនឡើងអេសអ៊ី [ខ្ញុំ] + ការថយចុះអេសអ៊ី [១] - ១ ហើយផ្ទុកវាទៅអូតូសិន។
  8. ត្រឡប់ឯកសារ ទិន្នផលអតិបរមា.

ការពន្យល់

អារេបញ្ចូលនៃទំហំ n មានចំនួនគត់វិជ្ជមាន។ យើងត្រូវបានស្នើសុំឱ្យរកលំដាប់ប៊ីតវែងបំផុតនៃអារេដែលបានផ្តល់ឱ្យ។ លំដាប់ហ្គីតាអាចត្រូវបានកំណត់ជាលំដាប់ដែលកើនឡើងដំបូងដែលមានន័យថាលេខនៅក្នុងលំដាប់កើនឡើងដំបូង។ បន្ទាប់មកចំនួនថយចុះរហូតដល់ចុងបញ្ចប់នៃលំដាប់។ យើងត្រូវកំណត់ប្រវែងនៃលំដាប់ហ្គីតាវែងបំផុត។

សូម​មើល​ផង​ដែរ
ម៉ាទ្រីសឌុយតេលាហ្សែនស៊ែរសឹបផ្លេយ

ដំបូងបំបែកដំណោះស្រាយជាពីរផ្នែក។ យើងប្រកាសអារេពីរអារេដំបូងត្រូវបានគេចាត់ទុកថាជាអា បង្កើនអេស អារេ។ លំដាប់កើនឡើងវែងបំផុតគឺជាលំដាប់ដែលលេខគួរតែជាលេខដំបូងនៅក្នុងលំដាប់កើនឡើង។ ដូច្នេះយើងនឹងឆ្លងកាត់អារេនៅក្នុងរង្វិលជុំដែលមានចលនា។ បន្តស្វែងរកការកើនឡើងជាបន្តបន្ទាប់។ បន្ទាប់មកយើងត្រូវពិនិត្យលក្ខខណ្ឌមួយថាប្រសិនបើធាតុបច្ចុប្បន្នតិចជាងធាតុបន្ទាប់។ ហើយធាតុបច្ចុប្បន្នរបស់អេសអេកកំពុងកើនឡើងតិចជាងធាតុបន្ទាប់នៃការកើនឡើងអេសអេច។ ប្រសិនបើពិតបន្ទាប់មករក្សាទុកធាតុដែលកំពុងកើនឡើងសឺច [ច] + ១ នេះបន្ថែមពីព្រោះយើងបានចាប់ផ្តើមតំរុយអារេ ១ នៅក្នុងវារួចហើយ។

ទីពីរប្រកាសអារេ ថយចុះអេស។ នៅក្នុងការថយចុះនេះយើងនឹងឆ្លងកាត់អារេនៅក្នុងរបៀបរង្វិលជុំពីស្តាំទៅឆ្វេងនៃអារេ។ យើងនឹងពិនិត្យមើលថាតើធាតុបច្ចុប្បន្នធំជាងធាតុបន្ទាប់។ ព្រោះយើងកំពុងដើរពីឆ្វេងទៅស្តាំ។ បន្ទាប់មកធ្វើបច្ចុប្បន្នភាពវាទៅការថយចុះអេសអ៊ី [i] ទៅការថយចុះអេសអេច [j] +១ ។ នៅជំហានចុងក្រោយនៃលេខកូដយើងត្រូវរកអតិបរិមានៃការបង្កើនអេសអេសអេស + ថយចុះអេសអ៊ី - ១ ដែលត្រូវបានរក្សាទុកនៅក្នុងមីអូតូ។

លេខកូដ  

លេខកូដ C ++ សម្រាប់បនា្ទាប់ប៊ីខនវែងបំផុត

#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

កូដចាវ៉ាសំរាប់បនា្ទាស់ប៊ីខនវែងបំផុត

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” គឺជាចំនួនធាតុក្នុងអារេ។ ចាប់តាំងពីយើងបានប្រើរង្វិលជុំនៅខាងស្តាំដែលធ្វើឱ្យក្បួនដោះស្រាយដំណើរការក្នុងពេលវេលាពហុធា។

សូម​មើល​ផង​ដែរ
ថ្លៃដើមអប្បបរមាសំរាប់កម្មករជួលខេ

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ចាប់តាំងពីយើងបានប្រើអារេបន្ថែមពីរដែលទំហំរបស់វាពឹងផ្អែកលើអារេបញ្ចូល។ ភាពស្មុគស្មាញនៃលំហគឺលីនេអ៊ែរ។