ວິທີແກ້ໄຂ Leetcode ສູງສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco ເຟສບຸກ Goldman Sachs ກູໂກ JPMorgan LinkedIn Microsoft Oracle PayPal Paytm Uber
Array ແບ່ງແລະເອົາຊະນະ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

ໃຫ້ຕົວເລກອາເລ່ ຈຳ ນວນ ໜຶ່ງ, ຊອກຫາຈຸດທີ່ຕິດຕໍ່ກັນ ໃຕ້ດິນ (ບັນຈຸມີຢ່າງ ໜ້ອຍ ໜຶ່ງ ຕົວເລກ) ເຊິ່ງມີ ຈຳ ນວນທີ່ໃຫຍ່ທີ່ສຸດແລະສົ່ງຄືນຍອດລວມຂອງມັນ.

ຍົກຕົວຢ່າງ

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

ຄໍາອະທິບາຍ:

[4, -1,2,1] ມີຍອດລວມໃຫຍ່ທີ່ສຸດ = 6.

nums = [-1]
-1

ວິທີທີ່ 1 (ແບ່ງອອກແລະເອົາຊະນະ)

ໃນວິທີການນີ້ພວກເຮົາຈະສົນທະນາກ່ຽວກັບການແບ່ງແຍກແລະເອົາຊະນະເຕັກນິກເພື່ອແກ້ໄຂບັນຫານີ້. ພວກເຮົາ ກຳ ລັງພະຍາຍາມຊອກຫາ subarray ທີ່ເຊື່ອມໂຍງເຊິ່ງມີຍອດລວມສູງສຸດ. ດັ່ງນັ້ນພວກເຮົາສາມາດເວົ້າໄດ້ວ່າ subarray ທີ່ດີທີ່ສຸດອາດຈະນອນຢູ່ໃນສ່ວນໃດສ່ວນຫນຶ່ງຂອງອາເລ. ດັ່ງນັ້ນພວກເຮົາເຮັດສາມກໍລະນີເຊິ່ງຈະກວມເອົາຄວາມເປັນໄປໄດ້ທັງ ໝົດ:

ກໍລະນີ 1:
subarray ສູງສຸດແມ່ນນອນຢູ່ໃນເຄິ່ງຊ້າຍຂອງອາເລ.
ກໍລະນີ 2:
subarray ສູງສຸດແມ່ນນອນຢູ່ໃນເຄິ່ງຂວາຂອງອາເລ.
ກໍລະນີ 3:
ບາງສ່ວນຂອງ subarray ສູງສຸດແມ່ນຢູ່ໃນເຄິ່ງຊ້າຍແລະສ່ວນອີກສ່ວນ ໜຶ່ງ ຂອງມັນແມ່ນຢູ່ໃນເຄິ່ງທີ່ສອງ (ຕົວຢ່າງ subarray ແມ່ນຂ້າມສ່ວນປະກອບກາງຂອງຂບວນ)

ດັ່ງທີ່ພວກເຮົາສາມາດເຫັນກໍລະນີທີ 1 ແລະກໍລະນີທີ 2 ແມ່ນພື້ນຖານໂຄງຮ່າງຍ່ອຍຂອງອາໄລ່ N / 2 ທີ່ມີຄວາມ ໝາຍ ດຽວກັນກັບບັນຫາຕົ້ນຕໍ. ບ່ອນທີ່ N ແມ່ນຂະ ໜາດ ຂອງຂບວນປະຈຸບັນ. ດັ່ງນັ້ນພວກເຮົາສາມາດເຮັດໄດ້ງ່າຍໆ ຮຽກຄືນ ຫນ້າທີ່ໃນໄລຍະສອງ halves ຂອງຂບວນການ.
ດຽວນີ້ສ່ວນທີ່ ສຳ ຄັນແມ່ນກໍລະນີທີ 3 ທີ່ພວກເຮົາຕ້ອງໄດ້ແກ້ໄຂໃນ ໜ້າ ທີ່ປະຈຸບັນແລະຫຼັງຈາກນັ້ນພວກເຮົາສາມາດສົ່ງຜົນລວມສູງສຸດຈາກ 3 ກໍລະນີນີ້.

ໃຫ້ເບິ່ງວ່າພວກເຮົາສາມາດແກ້ໄຂ ສຳ ລັບກໍລະນີທີ 3 ໄດ້ແນວໃດ:

ສົມມຸດວ່າພວກເຮົາມີ array = [-2,1, -3,4, -1,2,1, -5,4]
ພວກເຮົາຊອກຫາດັດສະນີກາງເພື່ອແບ່ງມັນອອກເປັນສອງສ່ວນເທົ່າກັນ.
ດັດສະນີກາງ = (0 + 9) / 2 = 4

ວິທີແກ້ໄຂ Leetcode ສູງສຸດ

ໃນຖານະເປັນກໍລະນີ 3 ແມ່ນການເວົ້າວ່າຜົນລວມສູງສຸດຈະຂ້າມອົງປະກອບກາງ. ດັ່ງນັ້ນພວກເຮົາຈະພະຍາຍາມຊອກຫາຍອດລວມທີ່ເລີ່ມຕົ້ນຕັ້ງແຕ່ກາງແລະສິ້ນສຸດຢູ່ເບື້ອງຊ້າຍ. ເຊັ່ນດຽວກັນພວກເຮົາຈະພົບກັບຍອດລວມທີ່ເລີ່ມຕົ້ນຈາກ (ກາງ + 1) ແລະສິ້ນສຸດຢູ່ເບື້ອງຂວາ. ໃນວິທີການນີ້ພວກເຮົາຈະພົບເຫັນ subarray ສູງສຸດທີ່ ກຳ ລັງຂ້າມຊາຍແດນກາງ ສຳ ລັບກໍລະນີທີ 3.

ສູດການຄິດໄລ່:

  • ແບ່ງອາເລເປັນສອງສ່ວນ.
  • ສືບຕໍ່ຊອກຫາຍອດ 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

ໂຄງການ Java

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບວິທີແກ້ໄຂ Leetcode ສູງສຸດ

ຄວາມສັບສົນເວລາ

O (NlogN): ໃນການແບ່ງແຍກແລະເອົາຊະນະຕົວຈິງພວກເຮົາ ກຳ ລັງແບ່ງປັນປັນຫາອອກເປັນສອງສ່ວນເທົ່າກັນຂອງຂະ ໜາດ N / 2. ອີກເທື່ອ ໜຶ່ງ ມັນແບ່ງອອກເປັນຂະ ໜາດ N / 4 ແລະອື່ນໆ. ເພາະສະນັ້ນລະດັບການເອີ້ນຄືນຢ່າງເລິກເຊິ່ງທີ່ສຸດຈະເປັນບ່ອນທີ່ຂະ ໜາດ ຂອງອາເລຈະ 1 ແລະພວກເຮົາ ກຳ ລັງກັບມາຈາກບ່ອນນັ້ນ. ໃນແຕ່ລະລະດັບພວກເຮົາ ກຳ ລັງເຮັດວຽກ O (n) ເພາະສະນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາທັງ ໝົດ ຈະເປັນ O (NlogN). ຕໍ່ໄປນີ້ແມ່ນການພົວພັນກັບການເກີດຂື້ນຄືນ ໃໝ່

ຄວາມສັບສົນໃນອະວະກາດ 

O (logN): ພື້ນທີ່ logN ຖືກໃຊ້ ສຳ ລັບການເອີ້ນຄືນ.

 

ວິທີການທີ 2 (ວິທີການຂອງ Kadane)

ວິທີການຂອງ Kadane ແມ່ນສູດການຄິດໄລ່ທີ່ມີຊື່ສຽງ ສຳ ລັບ sub array sum. ໃນວິທີການນີ້ພວກເຮົາພຽງແຕ່ເຮັດຊ້ ຳ ອີກເທື່ອ ໜຶ່ງ ເມື່ອທຽບໃສ່ຂບວນການປ້ອນຂໍ້ມູນໃຫ້. ພວກເຮົາເອົາລວມຍອດປັດຈຸບັນດ້ວຍຄ່າສູນແລະເພີ່ມແຕ່ລະສ່ວນປະກອບໃນເສັ້ນທາງ. ພວກເຮົາເພີ່ມແຕ່ລະອົງປະກອບໃສ່ຍອດລວມປັດຈຸບັນຖ້າຜົນລວມປັດຈຸບັນກ່ອນ ໜ້າ ນີ້ບໍ່ແມ່ນລົບຫລືບໍ່ດັ່ງນັ້ນພວກເຮົາພຽງແຕ່ ທຳ ລາຍຄວາມຕໍ່ເນື່ອງແລະປັບປຸງຜົນບວກກັບປັດໃຈປັດຈຸບັນ. ຄຽງຄູ່ກັບມັນຢູ່ໃນແຕ່ລະ ຕຳ ແໜ່ງ ພວກເຮົາກວດເບິ່ງວ່າຍອດລວມປັດຈຸບັນຍັງສູງສຸດທົ່ວໂລກຫຼືບໍ່ແລະປັບປຸງສູງສຸດທົ່ວໂລກຕາມນັ້ນ.

ສູດການຄິດໄລ່:

  • ສ້າງຕົວແປເພື່ອເກັບສູງສຸດຂອງໂລກ. ເລີ່ມຕົ້ນດ້ວຍ ຈຳ ນວນລົບຫຼາຍທີ່ສຸດ (INT_MIN).
  • ສ້າງຕົວແປເພື່ອເກັບຍອດລວມ. ເລີ່ມຕົ້ນດ້ວຍເລກສູນ.
  • ດໍາເນີນການ loop ຈາກຊ້າຍຫາຂວາຫຼາຍກວ່າ array ໄດ້. ຖ້າຜົນລວມປະຈຸບັນກາຍເປັນລົບ, ຫຼັງຈາກນັ້ນປັບປຸງມັນດ້ວຍຄ່າ 0.
  • ເພີ່ມປັດໃຈປັດຈຸບັນໃສ່ຍອດລວມປັດຈຸບັນແລະອັບເດດຍອດສູງສຸດທົ່ວໂລກຖ້າຜົນບວກປະຈຸບັນສູງກວ່າຍອດສູງສຸດຂອງໂລກ.
  • ສົ່ງຄືນສູງສຸດຂອງໂລກ.

ການປະຕິບັດ ສຳ ລັບການແກ້ໄຂບັນຫາ 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

ໂຄງການ Java

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບວິທີແກ້ໄຂ Leetcode ສູງສຸດ

ຄວາມສັບສົນເວລາ

O (N): ເນື່ອງຈາກວ່າມັນແມ່ນວິທີການຜ່ານລະບົບ ໜຶ່ງ.

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ບໍ່ມີຄວາມ ຈຳ ພິເສດຫຍັງໃຊ້.