ដំណោះស្រាយ Subarray Leetcode អតិបរិមា  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance ស៊ីស្កូ Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ក្រុមហ៊ុន JPMorgan LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle បានតាមរយៈការ Paytm Uber
ក្បួនដោះស្រាយ អារេ ការសរសេរកូដ ចែកនិងយកឈ្នះ ការសរសេរកម្មវិធីឌីណាមិក សំភាសន៍ កិច្ចសម្ភាសន៍ LeetCode LeetCodeSolutions

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

ដែលបានផ្តល់ឱ្យចំនួនអារេចំនួនរកឃើញជាប់គ្នា subarray (មានយ៉ាងហោចណាស់មួយលេខ) ដែលមានផលបូកធំបំផុតនិងប្រគល់ផលបូករបស់វាមកវិញ។

ឧទាហរណ៍

nums = [-2,1,-3,4,-1,2,1,-5,4]
6

ការពន្យល់:

[4, -1,2,1] មានផលបូកធំបំផុត = 6 ។

nums = [-1]
-1

វិធីសាស្រ្ត ១ (ការបែងចែកនិងយកឈ្នះ)  

នៅក្នុងវិធីសាស្រ្តនេះយើងនឹងពិភាក្សាអំពីការបែងចែកនិងយកឈ្នះបច្ចេកទេសដើម្បីដោះស្រាយបញ្ហានេះ។ យើងកំពុងព្យាយាមស្វែងរកផ្លូវក្រោមដីជាប់គ្នាដែលមានផលបូកអតិបរមា។ ដូច្នេះយើងអាចនិយាយបានថានាវាមុជទឹកដ៏ប្រសើរបំផុតអាចស្ថិតនៅផ្នែកណាមួយនៃអារេ។ ដូច្នេះយើងបង្កើតករណីចំនួន ៣ ដែលនឹងផ្តល់លទ្ធភាពទាំងអស់៖

ករណី 1:
subarray អតិបរមាស្ថិតនៅទាំងស្រុងនៅពាក់កណ្តាលខាងឆ្វេងនៃជួរអារេ។
ករណី 2:
subarray អតិបរមាស្ថិតនៅពាក់កណ្តាលខាងស្តាំនៃជួរអារេ។
ករណី 3:
ផ្នែកខ្លះនៃ subarray អតិបរិមាស្ថិតនៅពាក់កណ្តាលខាងឆ្វេងនិងផ្នែកមួយផ្នែកទៀតរបស់វាស្ថិតនៅពាក់កណ្តាលទីពីរ (ឧ។ subarray កំពុងឆ្លងកាត់ធាតុពាក់កណ្តាលនៃអារេ)

ដូចដែលយើងអាចឃើញករណីទី ១ និងករណីទី ២ ជាមូលដ្ឋានរងនៃជួរ N / 1 ដែលមាននិយមន័យដូចគ្នានឹងបញ្ហាចម្បង។ ដែល N ជាទំហំនៃអារេបច្ចុប្បន្ន។ ដូច្នេះយើងអាចធ្វើបានដោយសាមញ្ញ កើតឡើងវិញ មុខងារនៅលើពីរពាក់កណ្តាលនៃអារេ។
ផ្នែកសំខាន់គឺករណីទី ៣ ដែលយើងត្រូវដោះស្រាយក្នុងមុខងារបច្ចុប្បន្នហើយបន្ទាប់មកយើងអាចយកផលបូកអតិបរិមាចេញពីករណីទាំង ៣ នេះ។

សូម​មើល​ផង​ដែរ
ចំនួនបងប្អូនបង្កើតនៃថ្នាំងដែលបានផ្តល់ជាមែកធាង n-ary

អនុញ្ញាតឱ្យមើលពីរបៀបដែលយើងអាចដោះស្រាយសម្រាប់ករណីទី 3:

ឧបមាថាយើងមានអារេ = [-២,១, -៣,៤, ១,២,១, -៥,៤]
យើងរកឃើញសន្ទស្សន៍ពាក់កណ្តាលដើម្បីចែកវាជាពីរពាក់កណ្តាលស្មើគ្នា។
សន្ទស្សន៍ពាក់កណ្តាល = (០ + ៩) / ២ = ៤

ដំណោះស្រាយ Subarray Leetcode អតិបរិមា

ដូចករណីទី ៣ កំពុងនិយាយថាផលបូកអតិបរិមានឹងឆ្លងកាត់ធាតុពាក់កណ្តាល។ ដូច្នេះយើងនឹងព្យាយាមរកផលបូកអតិបរមាដែលចាប់ផ្តើមនៅពាក់កណ្តាលនិងបញ្ចប់នៅផ្នែកខាងឆ្វេង។ ស្រដៀងគ្នានេះដែរយើងនឹងរកឃើញផលបូកអតិបរិមាដែលចាប់ផ្តើមពី (ពាក់កណ្តាល + ១) និងបញ្ចប់នៅខាងស្តាំ។ តាមវិធីនេះយើងនឹងរកឃើញនូវខ្សែរថភ្លើងក្រោមបំផុតដែលកំពុងឆ្លងកាត់ព្រំដែនពាក់កណ្តាលសម្រាប់ករណីទី ៣ ។

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

  • ចែកអារេជាពីរពាក់កណ្តាល។
  • រកឃើញផលបូករង subarray អតិបរមាសម្រាប់ subarray ខាងឆ្វេង។
  • រកឃើញផលបូករង subarray អតិបរមាសម្រាប់ subarray ខាងស្តាំ។
  • រកផលបូករង subarray អតិបរមាដែលឆ្លងកាត់ចំណុចកណ្តាល។
  • ត្រឡប់ចំនួនអតិបរមាខាងលើចំនួនបី។

ការអនុវត្តសម្រាប់ដំណោះស្រាយ Subarray Leetcode អតិបរិមា

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

int helper(int i,int j, vector<int>& nums)
{
    if(i==j) return nums[i];
    int left_cross=INT_MIN, right_cross=INT_MIN;

    int mid= (i+j)/2;
    int cur=0;
    for(int k=mid+1;k<=j;k++)
    {
        cur+= nums[k];
        right_cross= max(right_cross,cur);
    }

    cur=0;
    for(int k=mid;k>=i;k--)
    {
        cur+= nums[k];
        left_cross= max(left_cross,cur);
    }

    int cross_sum = left_cross + right_cross;
    int left_sum  = helper(i,mid,nums);
    int right_sum = helper(mid+1,j,nums);

    return max( cross_sum , max(left_sum , right_sum) );
}

int maxSubArray(vector<int>& nums) {
    return helper(0,nums.size()-1,nums);
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

កម្មវិធីចាវ៉ា

class Rextester{
    
  static int helper(int i,int j, int[] nums)
    { 
        if(i==j) return nums[i];       
        int left_cross=Integer.MIN_VALUE, right_cross=Integer.MIN_VALUE;
        
        int mid= (i+j)/2;
        int cur=0;
        for(int k=mid+1;k<=j;k++)
        {
            cur+= nums[k];
            right_cross= Math.max(right_cross,cur);
        }
        
        cur=0;
        for(int k=mid;k>=i;k--)
        {
            cur+= nums[k];
            left_cross= Math.max(left_cross,cur);
        }
        
        int cross_sum=  left_cross + right_cross; 
        int left_sum = helper(i,mid,nums);
        int right_sum = helper(mid+1,j,nums);
        
        return Math.max( cross_sum , Math.max(left_sum , right_sum) );        
    }
    
    public static int maxSubArray(int[] nums) {
        return helper(0,nums.length-1,nums);
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយ Subarray Leetcode អតិបរិមា

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

O (NlogN)៖ នៅក្នុងការបែងចែកនិងយកឈ្នះតាមពិតយើងកំពុងបែងចែកបញ្ហាទៅជាពាក់កណ្ដាលស្មើគ្នានៃទំហំ N / 2 ។ ជាថ្មីម្តងទៀតវាត្រូវបានបែងចែកជាទំហំ N / 4 និងផ្សេងទៀត។ ដូច្នេះកម្រិតជ្រៅបំផុតនៃការហៅខ្លួនឯងនឹងមានជាកន្លែងដែលទំហំអារេនឹងមាន ១ ហើយយើងកំពុងត្រឡប់មកពីទីនោះ។ នៅកម្រិតនីមួយៗដែលយើងកំពុងបំពេញការងារ O (n) ដូចនេះភាពស្មុគស្មាញពេលវេលាសរុបគឺ O (NlogN) ។ នៅទីនេះទំនាក់ទំនងកើតឡើងដដែលៗ

សូម​មើល​ផង​ដែរ
បន្ថែមនិងស្វែងរកពាក្យ - រចនារចនាសម្ព័ន្ធទិន្នន័យ LeetCode

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

O (logN)៖ ចន្លោះ logN ត្រូវបានប្រើសម្រាប់ជង់នៃការហៅខ្លួនឯង។

 

វិធីសាស្រ្ត ២ (វិធីសាស្ត្ររបស់កាដាណេ)  

វិធីសាស្រ្តរបស់ Kadane គឺជាក្បួនដោះស្រាយដ៏ល្បីល្បាញសំរាប់ផលបូកអារេរង។ នៅក្នុងវិធីសាស្រ្តនេះយើងគ្រាន់តែនិយាយម្តងហើយម្តងទៀតលើអារេបញ្ចូលដែលបានផ្តល់។ ដំបូងយើងយកផលបូកបច្ចុប្បន្នជាមួយតម្លៃសូន្យហើយបន្ថែមធាតុនីមួយៗនៅក្នុងផ្លូវ។ យើងបន្ថែមធាតុនីមួយៗទៅផលបូកបច្ចុប្បន្នប្រសិនបើផលបូកបច្ចុប្បន្នមិនអវិជ្ជមានបើមិនដូច្នេះទេយើងគ្រាន់តែបំបែកការបន្តនិងធ្វើបច្ចុប្បន្នភាពផលបូកបច្ចុប្បន្នជាមួយធាតុបច្ចុប្បន្ន។ រួមជាមួយវានៅទីតាំងនីមួយៗយើងពិនិត្យមើលថាតើផលបូកបច្ចុប្បន្នក៏ជាចំនួនអតិបរមាសកលឬអត់ហើយធ្វើបច្ចុប្បន្នភាពអតិបរមាជាសកលយោងទៅតាមនោះ។

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

  • បង្កើតអថេរដើម្បីផ្ទុកអតិបរមាជាសកល។ ចាប់ផ្តើមជាមួយលេខអវិជ្ជមានបំផុត (INT_MIN) ។
  • បង្កើតអថេរដើម្បីរក្សាទុកផលបូកបច្ចុប្បន្ន។ ចាប់ផ្តើមជាមួយសូន្យ។
  • រត់រង្វិលជុំពីឆ្វេងទៅស្តាំលើអារេ។ ប្រសិនបើផលបូកបច្ចុប្បន្នប្រែជាអវិជ្ជមានបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពវាដោយតម្លៃ ០ ។
  • បន្ថែមធាតុបច្ចុប្បន្នទៅផលបូកបច្ចុប្បន្ននិងធ្វើបច្ចុប្បន្នភាពអតិបរមាជាសកលប្រសិនបើផលបូកបច្ចុប្បន្នធំជាងអតិបរិមាសកល។
  • ត្រឡប់អតិបរមាជាសកល។

ការអនុវត្តសម្រាប់ដំណោះស្រាយ Subarray Leetcode អតិបរិមា

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int>& nums) 
{
    int max_sum=INT_MIN;
    int cur=0;
    for(auto x:nums)
    {
        if(cur<0) cur=0;
        cur += x;
        max_sum =  max(max_sum , cur);
    }
    return max_sum;
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

កម្មវិធីចាវ៉ា

class Rextester{
  
    public static int maxSubArray(int[] nums) 
    {
        int max_sum = Integer.MIN_VALUE;
        int cur=0;
        for(int x:nums)
        {
            if(cur<0) cur=0;
            cur += x;
            max_sum =  Math.max(max_sum , cur);
        }
        return max_sum;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយ Subarray Leetcode អតិបរិមា

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

O (N)៖ ដោយសារវាជាក្បួនដោះស្រាយឆ្លងកាត់មួយលើអារេ។

សូម​មើល​ផង​ដែរ
ដំណោះស្រាយលេខសេស Leetcode ជាប់គ្នាចំនួនបី

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

O (១)៖ គ្មានអង្គចងចាំបន្ថែមត្រូវបានប្រើ។

1