Subarray វែងបំផុតមានចំនួនរាប់ពីមួយទៅមួយច្រើនជាងចំនួនលេខ ០  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ Accenture ក្រុមហ៊ុន Amazon ឌីសៅ ក្រុមហ៊ុន Samsung
អារេ ហាស់

យើងបានផ្តល់ឱ្យ អារេ នៃចំនួនគត់។ អារេមានតែលេខ ១ និងលេខ ០ ប៉ុណ្ណោះ។ សេចក្តីថ្លែងបញ្ហាស្នើឱ្យស្វែងយល់ពីប្រវែងនៃ Sub-Array ដែលវែងបំផុតដែលមានបរិមាណនៃលេខ ១ គឺគ្រាន់តែជាចំនួនមួយច្រើនជាងចំនួន ០ នៅក្នុងអារេរងមួយ។

ឧទាហរណ៍  

បញ្ចូល:

មកដល់ [] = {1,0,1,1,0,0,0}

លទ្ធផល:

5

ការពន្យល់:

ចាប់ពី ០ ដល់ ៤ សន្ទស្សន៍ {១, ០, ១, ១} មាន ៣ ១ និង ២ ០។ គ្រាន់តែរាប់មួយក្នុងចំណោមលេខ ១ នៃលេខ ០ ។

បញ្ចូល:

មកដល់ [] = {1,0,1,0,0}

លទ្ធផល:

3

ការពន្យល់:

ចាប់ពី ០ ដល់ ២ សន្ទស្សន៍ {១, ០, ១} មាន ២ ១ និងមួយ ០ ។ គ្រាន់តែរាប់មួយក្នុងចំណោមលេខ ១ នៃលេខ ០ ។

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

  1. ប្រកាសផែនទី។
  2. កំណត់ផលបូកនិងប្រវែងលទ្ធផលដល់ ០ ។
  3. ឆ្លងកាត់អារេខណះពេលដែល i = 0 ដល់ i <n ។
    1. ពិនិត្យមើលថាតើអា [អ៊ី] ស្មើនឹង ០ ប្រសិនបើពិតអញ្ចឹងបន្ថែម ១ បូក។
    2. ផ្សេងទៀតបន្ថែម +1 ទៅបូក។
    3. ពិនិត្យមើលថាតើ ផលបូកស្មើ ទៅ ១ បន្ទាប់មកបង្កើនតម្លៃនៃប្រវែងលទ្ធផល ១ ។
    4. ម៉្យាងទៀតពិនិត្យមើលថាតើផែនទីមួយដែលមិនមានផលបូកបើពិតបន្ទាប់មកដាក់បូកនិងតម្លៃបច្ចុប្បន្នរបស់ខ្ញុំទៅផែនទីរួមជាមួយការបូក។
    5. ពិនិត្យមើលថាតើផែនទីមាន (ផលបូក ១) ។
    6. ប្រសិនបើប្រវែងលទ្ធផលតិចជាងសន្ទស្សន៍អាយ (សន្ទស្សន៍ផលបូកនៅក្នុងផែនទី) ។
      1. ប្រសិនបើពិតបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពប្រវែងលទ្ធផលទៅអាយ - សន្ទស្សន៍។
  4. ត្រឡប់ប្រវែងលទ្ធផល។
សូម​មើល​ផង​ដែរ
អារេគោលពីរបន្ទាប់ពីប្រតិបត្ដិការបិទបើកជួរ M

ការពន្យល់  

យើងនឹងប្រកាសក ផែនទី។ នៅក្នុងផែនទីនោះយើងនឹងរក្សាទុកតម្លៃនៃផលបូកនិងតម្លៃបច្ចុប្បន្ននៃសន្ទស្សន៍ប្រសិនបើលក្ខខណ្ឌពេញចិត្ត។ យកអថេរពីរនិងកំណត់ផលបូកទៅ ០ និងលទ្ធផលប្រវែងដល់ ០ ។ ខណៈពេលឆ្លងកាត់អារេយើងនឹងជ្រើសរើសធាតុនីមួយៗនៃអារេហើយពិនិត្យមើលថាតើ [[]] ស្មើនឹង ០ ប្រសិនបើរកឃើញថាវាស្មើយើងនឹងបន្ថែម -0 ដើម្បីបូកនិងរក្សាទុកវាដើម្បីបូកបើមិនរកឃើញថាយើង 0 យើងនឹងបន្ថែមវិជ្ជមាន ១ ទៅផលបូកហើយរក្សាទុកវាដើម្បីបូក។

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

ឧបមាថាយើងនឹងយក ១, ០, ១ ប្រសិនបើយើងធ្វើពុតលេខ ០ ជា -១ យើងនឹងទទួលបានលេខ ០ នោះដែលមាន ២ ខ្ទង់ដំបូងហើយជាមួយលេខទីបីយើងអាចឃើញថាលក្ខខណ្ឌរបស់យើងត្រូវបានបំពេញ។ យើងទទួលបានអនុជួរមួយនៃលេខ ១ និងលេខ ០ ដោយមានការរាប់មួយបន្ថែមពី ១ ដល់ ០ ។ យើងធ្វើអោយស្ថានភាពរបស់យើងពេញចិត្ត។ នោះហើយជាមូលហេតុដែលយើងនឹងស្វែងរកប្រសិនបើផលបូកស្មើនឹង ១ នៅជំហានបន្ទាប់នៃក្បួនដោះស្រាយហើយនឹងត្រូវបានធ្វើបច្ចុប្បន្នភាពប្រវែងនៃប្រវែងលទ្ធផល។ នៅចុងក្រោយប្រសិនបើសេចក្តីថ្លែងការណ៍ប្រសិនបើយើងទទួលបានប្រវែងលទ្ធផលថ្មីយើងត្រូវធ្វើបច្ចុប្បន្នភាពលទ្ធផលមុនជាមួយនឹងប្រវែងលទ្ធផលបច្ចុប្បន្នហើយយើងនឹងត្រឡប់ប្រវែងលទ្ធផល។

សូម​មើល​ផង​ដែរ
ស្វែងរកធាតុស្ទួន

ការអនុវត្តន៍  

កម្មវិធី C ++ សម្រាប់ Subarray វែងបំផុតមានចំនួនរាប់ចាប់ពី ១ លេខច្រើនជាងចំនួនលេខ ០

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

កម្មវិធីចាវ៉ាសំរាប់ Subarray វែងជាងគេមានចំនួន ១ លេខច្រើនជាងចំនួនលេខ ០

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

ការវិភាគស្មុគស្មាញសម្រាប់ Subarray វែងបំផុតមានចំនួន ១ លេខ ១ ច្រើនជាងចំនួនលេខ ០  

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

អូរ (n) ដែលជាកន្លែងដែល “ n”  គឺជាចំនួនធាតុក្នុងអារេ។

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

អូរ (n) ដែលជាកន្លែងដែល “ n”  គឺជាចំនួនធាតុក្នុងអារេ។