Subarray ផលិតផលអតិបរមា


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ស៊ីស្កូ ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley Myntra PayU អ៊ិនធឺណិតដង។ Zoho
អារេ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា "Subarray ផលិតផលអតិបរមា" បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ អារេ នៃចំនួនគត់មានទាំងលេខវិជ្ជមាននិងអវិជ្ជមាន។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យរកផលិតផលអតិបរមានៃអារេរង។

ឧទាហរណ៍

arr[] = { 2, -2, 3, 5}
15

ការពន្យល់

ធាតុនៅក្នុងអារេរងគឺ ៣ និង ៥ ដែលផ្ទុកផលិតផលអតិបរមានៃអនុជួរដែលអាចធ្វើបាន។

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

1. Traverse the array from i = 0 to less than the value n(length of the given array).
  1. Check if arr[i] is greater than 0, if true
    1. Find out the maximumRange by multiplying each value of an array to itself.
    2. Find out the minimumRange between the product of minimumRange and arr[i] and 1.
    3. Mark flag is equal to 1.
  2. If the value of the array is equal to 0, then mark the minimum and maximum range to 1.
  3. Else find out the maximum between the product of minimumRange and arr[i] and 1 and find out the minimumRange by the product value of maximumRange and arr[i].
  4. If maxValue is less than the value of the maximumRange then store the value of maximumRange to maxValue.’
2. Check if the flag is equal to 0 and also maxValue is equal to 1, then return 0
3. Return maxValue.

ការពន្យល់

យើងបានផ្តល់ឱ្យ អារេ of ចំនួនគត់។ យើងបានស្នើសុំឱ្យរកផលិតផលអតិបរិមាដែលអារេរងអាចកាន់កាប់នៅក្នុងអារេដែលបានផ្តល់ឱ្យ។ អារេមានទាំងលេខវិជ្ជមាននិងអវិជ្ជមាន។ យើងគ្រាន់តែត្រូវរកផលិតផលអតិបរមានៅទីនេះ។ វិធីសាស្រ្តដែលយើងកំពុងប្រើនៅទីនេះគឺស្មើនឹងប្រវែងអតិបរមានៃអារេរងដែលជាផលបូកអតិបរមាឬផលិតផលអតិបរមា។

ឥលូវនេះយើងគ្រាន់តែផ្តោតលើផលិតផលអតិបរិមាដែលអាចត្រូវបានផលិតដោយប្រើអនុក្រោមទាំងអស់។ យើងនឹងមានការចាប់អារម្មណ៍យ៉ាងខ្លាំងទៅលើកំរិតអតិបរមានិងអប្បបរមា។ នៅ maxValue យើងនឹងរក្សាទុកផលិតផលអតិបរមានៅទីនេះ។ ទង់គឺជាអថេរដើម្បីពិនិត្យមើលថាតើយើងបានរកឃើញលេខវិជ្ជមានណាមួយហើយក៏មានផលិតផលអតិបរិមាក្រៅពីលេខ ១ ។

យើងនឹងឆ្លងកាត់អារេពី ០ ទៅ n (ដែល n ជាប្រវែងនៃអារេ) ។ យើងនឹងពិនិត្យមើលថាតើ arr [i] ធំជាង ០ ។ ប្រសិនបើវាជាការពិតបន្ទាប់មកស្តុកទុកផលិតផលនៃអាំងតេក្រាលហើយមកដល់ [i] ទៅក្នុងហ្វ្រេមខន។ បន្ទាប់មកស្វែងយល់ពីតម្លៃអប្បបរមារវាងផលិតផលនៃអាន់ជេនខននិងមកដល់ [អាយ] និងលេខ ១ ហើយរក្សាទុកវាទៅអប្បបរមាលីនថេន។

បន្ទាប់ពីនោះវានឹងមានលក្ខខណ្ឌមួយផ្សេងទៀតប្រសិនបើធាតុអារេណាមួយនៅក្នុងតំបន់រងគឺ ០ បន្ទាប់មកសម្គាល់តម្លៃអប្បបរមានិងតម្លៃអតិបរមាទៅ ១. បន្ទាប់មកយើងទើបតែចាប់ផ្តើមពីទីនេះ។

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

Subarray ផលិតផលអតិបរមា

លេខកូដ

លេខកូដគណបក្សប្រជាជនដើម្បីស្វែងរក Subarray ផលិតផលអតិបរមា

#include<iostream>

using namespace std;

int maxSubarrayProduct(int arr[], int n)
{
    int maximumRange = 1;
    int minimumRange = 1;

    int maxValue = 1;
    int flag = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > 0)
        {
            maximumRange = maximumRange * arr[i];
            minimumRange = min(minimumRange * arr[i], 1);
            flag = 1;
        }
        else if (arr[i] == 0)
        {
            maximumRange = 1;
            minimumRange = 1;
        }
        else
        {
            int temp = maximumRange;
            maximumRange = max(minimumRange * arr[i], 1);
            minimumRange = temp * arr[i];
        }
        if (maxValue < maximumRange)
            maxValue = maximumRange;
    }
    if (flag == 0 && maxValue == 1)
        return 0;
    return maxValue;
}
int main()
{
    int arr[] = { 2,-2,-3,-5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Sub array product is "<< maxSubarrayProduct(arr, n);
    return 0;
}
Maximum Sub array product is 15

កូដចាវ៉ាដើម្បីស្វែងរក Subarray ផលិតផលអតិបរិមា

class productSubarray
{
    public static int maxSubarrayProduct(int arr[])
    {
        int n = arr.length;
        int maximumRange = 1;
        int minimumRange = 1;

        int maxValue = 1;
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > 0)
            {
                maximumRange = maximumRange * arr[i];
                minimumRange = Math.min(minimumRange * arr[i], 1);
                flag = 1;
            }
            else if (arr[i] == 0)
            {
                maximumRange = 1;
                minimumRange = 1;
            }
            else
            {
                int temp = maximumRange;
                maximumRange = Math.max(minimumRange * arr[i], 1);
                minimumRange = temp * arr[i];
            }
            if (maxValue < maximumRange)
                maxValue = maximumRange;
        }
        if (flag == 0 && maxValue == 1)
            return 0;
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,-2,-3,-5};
        System.out.println("Maximum Sub array product is "+ maxSubarrayProduct(arr));
    }
}
Maximum Sub array product is 15

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ដោយសារតែយើងដំណើរការរង្វិលជុំលើធាតុនៅក្នុងអារេ។ ពេលវេលាសរុបដែលបានយកសម្រាប់ក្បួនដោះស្រាយដើម្បីដំណើរការគឺលីនេអ៊ែរ។

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

ឱ (១) ដោយមិនចាំបាច់មានទំហំបន្ថែម។ ដោយសារតែយើងមិនបានរក្សាទុកទិន្នន័យសម្រាប់ធាតុនីមួយៗ។ ជំនួសឱ្យការធ្វើដែលយើងបានប្រើចន្លោះថេរហើយដូច្នេះភាពស្មុគស្មាញនៃលំហគឺថេរ។