ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಸಿಸ್ಕೋ ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ JP ಮೋರ್ಗಾನ್ ಸಂದೇಶ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಪೇಪಾಲ್ ಪೇಟ್ಮ್ ಉಬರ್
ಅಲ್ಗಾರಿದಮ್ಗಳು ಅರೇ ಕೋಡಿಂಗ್ ಭಾಗಿಸಿ ಜಯಿಸಿ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ  

ಒಂದು ಪೂರ್ಣಾಂಕ ಶ್ರೇಣಿಯ ಸಂಖ್ಯೆಗಳನ್ನು ನೀಡಿದರೆ, ಸಮೀಪವನ್ನು ಹುಡುಕಿ ಸಬ್‌ರೇ (ಕನಿಷ್ಠ ಒಂದು ಸಂಖ್ಯೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ) ಇದು ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಅದರ ಮೊತ್ತವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ:

[4, -1,2,1] ಅತಿದೊಡ್ಡ ಮೊತ್ತ = 6 ಅನ್ನು ಹೊಂದಿದೆ.

nums = [-1]
-1

ಅಪ್ರೋಚ್ 1 (ಭಾಗಿಸಿ ಜಯಿಸಿ)  

ಈ ವಿಧಾನದಲ್ಲಿ ನಾವು ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ತಂತ್ರದ ಬಗ್ಗೆ ಚರ್ಚಿಸುತ್ತೇವೆ. ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ಆ ಸಬ್‌ಅರೇ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಪ್ರಯತ್ನಿಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಶ್ರೇಣಿಯ ಯಾವುದೇ ಭಾಗದಲ್ಲಿ ಗರಿಷ್ಠ ಸಬ್‌ಅರೇ ಇರುತ್ತದೆ ಎಂದು ನಾವು ಹೇಳಬಹುದು. ಆದ್ದರಿಂದ ನಾವು ಮೂರು ಪ್ರಕರಣಗಳನ್ನು ಮಾಡುತ್ತೇವೆ ಅದು ಎಲ್ಲಾ ಸಾಧ್ಯತೆಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ:

ಕೇಸ್ 1:
ರಚನೆಯ ಎಡಭಾಗದಲ್ಲಿ ಮ್ಯಾಕ್ಸ್ ಸಬ್‌ರೇ ಸಂಪೂರ್ಣವಾಗಿ ಇರುತ್ತದೆ.
ಕೇಸ್ 2:
ಮ್ಯಾಕ್ಸ್ ಸಬ್‌ರೇರೇ ಸಂಪೂರ್ಣವಾಗಿ ರಚನೆಯ ಬಲ ಭಾಗದಲ್ಲಿದೆ.
ಕೇಸ್ 3:
ಗರಿಷ್ಠ ಸಬ್‌ಅರ್ರೆಯ ಭಾಗಶಃ ಭಾಗವು ಎಡ ಅರ್ಧದಲ್ಲಿದೆ ಮತ್ತು ಅದರ ಇನ್ನೊಂದು ಭಾಗವು ದ್ವಿತೀಯಾರ್ಧದಲ್ಲಿದೆ (ಅಂದರೆ ಸಬ್‌ಅರೇ ರಚನೆಯ ಮಧ್ಯದ ಅಂಶವನ್ನು ದಾಟುತ್ತಿದೆ)

ನಾವು ನೋಡುವಂತೆ ಕೇಸ್ 1 ಮತ್ತು ಕೇಸ್ 2 ಮೂಲತಃ ಮುಖ್ಯ ಸಮಸ್ಯೆಯಂತೆಯೇ ವ್ಯಾಖ್ಯಾನವನ್ನು ಹೊಂದಿರುವ ಎನ್ / 2 ಗಾತ್ರದ ರಚನೆಯ ಉಪಪ್ರೋಬ್ಲಮ್ ಆಗಿದೆ. ಇಲ್ಲಿ N ಎಂಬುದು ಪ್ರಸ್ತುತ ರಚನೆಯ ಗಾತ್ರವಾಗಿದೆ. ಆದ್ದರಿಂದ ನಾವು ಸರಳವಾಗಿ ಮಾಡಬಹುದು ಮನವಿಯನ್ನು ರಚನೆಯ ಎರಡು ಭಾಗಗಳ ಮೇಲಿನ ಕಾರ್ಯ.
ಈಗ ಮುಖ್ಯ ಭಾಗವೆಂದರೆ ಕೇಸ್ 3, ಇದನ್ನು ನಾವು ಪ್ರಸ್ತುತ ಕಾರ್ಯದಲ್ಲಿ ಪರಿಹರಿಸಬೇಕಾಗಿದೆ ಮತ್ತು ನಂತರ ನಾವು ಈ 3 ಪ್ರಕರಣಗಳಲ್ಲಿ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಹಿಂತಿರುಗಿಸಬಹುದು.

ಸಹ ನೋಡಿ
ಎನ್-ಆರಿ ಟ್ರೀನಲ್ಲಿ ನಿರ್ದಿಷ್ಟ ನೋಡ್ನ ಒಡಹುಟ್ಟಿದವರ ಸಂಖ್ಯೆ

ಪ್ರಕರಣ 3 ಕ್ಕೆ ನಾವು ಹೇಗೆ ಪರಿಹರಿಸಬಹುದು ಎಂಬುದನ್ನು ನೋಡೋಣ:

ನಮ್ಮಲ್ಲಿ ಅರೇ = [-2,1, -3,4, -1,2,1, -5,4] ಇದೆ ಎಂದು ಭಾವಿಸೋಣ
ಮಧ್ಯ ಸೂಚ್ಯಂಕವನ್ನು ಎರಡು ಸಮಾನ ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಲು ನಾವು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ.
ಮಧ್ಯ ಸೂಚ್ಯಂಕ = (0 + 9) / 2 = 4

ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಕೇಸ್ 3 ಹೇಳುವಂತೆ ಗರಿಷ್ಠ ಮೊತ್ತವು ಮಧ್ಯದ ಅಂಶವನ್ನು ದಾಟುತ್ತದೆ. ಆದ್ದರಿಂದ ನಾವು ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಮಧ್ಯದಿಂದ ಪ್ರಾರಂಭಿಸಿ ಎಡಭಾಗದಲ್ಲಿ ಕೊನೆಗೊಳಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಅದೇ ರೀತಿ ನಾವು ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು (ಮಧ್ಯ +1) ಪ್ರಾರಂಭಿಸಿ ಬಲಭಾಗದಲ್ಲಿ ಕೊನೆಗೊಳಿಸುತ್ತೇವೆ. ಈ ರೀತಿಯಾಗಿ ನಾವು ಕೇಸ್ 3 ಗಾಗಿ ಮಧ್ಯದ ಗಡಿಯನ್ನು ದಾಟುತ್ತಿರುವ ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಅನ್ನು ಕಾಣುತ್ತೇವೆ.

ಅಲ್ಗಾರಿದಮ್:

  • ರಚನೆಯನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಿ.
  • ಎಡ ಸಬ್‌ರೇರ್‌ಗಾಗಿ ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಮೊತ್ತವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಹುಡುಕಿ.
  • ಬಲ ಸಬ್‌ರೇರ್‌ಗಾಗಿ ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಮೊತ್ತವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಹುಡುಕಿ.
  • ಮಧ್ಯದ ಬಿಂದುವನ್ನು ದಾಟುವ ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಮೊತ್ತವನ್ನು ಹುಡುಕಿ.
  • ಮೇಲಿನ ಮೂರು ಮೊತ್ತದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಹಿಂತಿರುಗಿ.

ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

O (NlogN): ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವಲ್ಲಿ ನಾವು ಸಮಸ್ಯೆಯನ್ನು N / 2 ಗಾತ್ರದ ಎರಡು ಸಮಾನ ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತಿದ್ದೇವೆ. ಮತ್ತೆ ಅದು N / 4 ಗಾತ್ರದಲ್ಲಿ ವಿಭಜನೆಯಾಗುತ್ತಿದೆ. ಆದ್ದರಿಂದ ಪುನರಾವರ್ತನೆಯ ಆಳವಾದ ಮಟ್ಟವು ಲಾಗ್‌ಎನ್ ಆಗಿರುತ್ತದೆ, ಅಲ್ಲಿ ರಚನೆಯ ಗಾತ್ರವು 1 ಆಗಿರುತ್ತದೆ ಮತ್ತು ನಾವು ಅಲ್ಲಿಂದ ಹಿಂತಿರುಗುತ್ತಿದ್ದೇವೆ. ಪ್ರತಿ ಹಂತದಲ್ಲಿ ನಾವು O (n) ಕಾರ್ಯವನ್ನು ಮಾಡುತ್ತಿದ್ದೇವೆ ಆದ್ದರಿಂದ ಒಟ್ಟು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (NlogN) ಆಗಿರುತ್ತದೆ. ಇಲ್ಲಿ ಮರುಕಳಿಸುವ ಸಂಬಂಧವಿದೆ

ಸಹ ನೋಡಿ
ಪದವನ್ನು ಸೇರಿಸಿ ಮತ್ತು ಹುಡುಕಿ - ಡೇಟಾ ರಚನೆ ವಿನ್ಯಾಸ ಲೀಟ್‌ಕೋಡ್

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಲಾಗ್ ಎನ್): ಲಾಗ್ ಎನ್ ಜಾಗವನ್ನು ಪುನರಾವರ್ತಿತ ಸ್ಟ್ಯಾಕ್ಗಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ.

 

ಅಪ್ರೋಚ್ 2 (ಕಡಾನೆ ವಿಧಾನ)  

ಕಡಾನೆ ವಿಧಾನವು ಉಪ ಶ್ರೇಣಿಯ ಮೊತ್ತಕ್ಕೆ ಪ್ರಸಿದ್ಧ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಈ ವಿಧಾನದಲ್ಲಿ ನಾವು ಕೊಟ್ಟಿರುವ ಇನ್ಪುಟ್ ರಚನೆಯ ಮೇಲೆ ಒಮ್ಮೆ ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ. ನಾವು ಪ್ರಸ್ತುತ ಮೊತ್ತವನ್ನು ಶೂನ್ಯ ಮೌಲ್ಯದೊಂದಿಗೆ ಪ್ರಾರಂಭದಲ್ಲಿ ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿ ಅಂಶವನ್ನು ಹಾದಿಯಲ್ಲಿ ಸೇರಿಸುತ್ತೇವೆ. ಹಿಂದಿನ ಪ್ರಸ್ತುತ ಮೊತ್ತವು negative ಣಾತ್ಮಕವಾಗಿಲ್ಲದಿದ್ದರೆ ನಾವು ಪ್ರತಿ ಅಂಶವನ್ನು ಪ್ರಸ್ತುತ ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸುತ್ತೇವೆ ಅಥವಾ ಇಲ್ಲದಿದ್ದರೆ ನಾವು ನಿರಂತರತೆಯನ್ನು ಮುರಿದು ಪ್ರಸ್ತುತ ಮೊತ್ತವನ್ನು ಪ್ರಸ್ತುತ ಅಂಶದೊಂದಿಗೆ ನವೀಕರಿಸುತ್ತೇವೆ. ಪ್ರತಿ ಸ್ಥಾನದಲ್ಲಿ ಅದರೊಂದಿಗೆ ನಾವು ಪ್ರಸ್ತುತ ಮೊತ್ತವು ಜಾಗತಿಕ ಗರಿಷ್ಠವಾಗಿದೆಯೆ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ ಮತ್ತು ಅದಕ್ಕೆ ಅನುಗುಣವಾಗಿ ಜಾಗತಿಕ ಗರಿಷ್ಠತೆಯನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ.

ಅಲ್ಗಾರಿದಮ್:

  • ಜಾಗತಿಕ ಗರಿಷ್ಠವನ್ನು ಸಂಗ್ರಹಿಸಲು ವೇರಿಯೇಬಲ್ ಅನ್ನು ರಚಿಸಿ. ಹೆಚ್ಚಿನ negative ಣಾತ್ಮಕ ಸಂಖ್ಯೆಯೊಂದಿಗೆ (INT_MIN) ಪ್ರಾರಂಭಿಸಿ.
  • ಪ್ರಸ್ತುತ ಮೊತ್ತವನ್ನು ಸಂಗ್ರಹಿಸಲು ವೇರಿಯೇಬಲ್ ಅನ್ನು ರಚಿಸಿ. ಶೂನ್ಯದೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸಿ.
  • ರಚನೆಯ ಮೇಲೆ ಎಡದಿಂದ ಬಲಕ್ಕೆ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ. ಪ್ರಸ್ತುತ ಮೊತ್ತವು negative ಣಾತ್ಮಕವಾಗಿದ್ದರೆ ಅದನ್ನು ಮೌಲ್ಯ 0 ನೊಂದಿಗೆ ನವೀಕರಿಸಿ.
  • ಪ್ರಸ್ತುತ ಮೊತ್ತವನ್ನು ಪ್ರಸ್ತುತ ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸಿ ಮತ್ತು ಪ್ರಸ್ತುತ ಮೊತ್ತವು ಜಾಗತಿಕ ಗರಿಷ್ಠಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ ಜಾಗತಿಕ ಗರಿಷ್ಠತೆಯನ್ನು ನವೀಕರಿಸಿ.
  • ಜಾಗತಿಕ ಗರಿಷ್ಠ ಹಿಂತಿರುಗಿ.

ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಗರಿಷ್ಠ ಸಬ್‌ರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್): ಇದು ರಚನೆಯ ಮೇಲೆ ಒಂದು ಪಾಸ್ ಅಲ್ಗಾರಿದಮ್ ಆಗಿರುವುದರಿಂದ.

ಸಹ ನೋಡಿ
ಮೂರು ಸತತ ಆಡ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (1): ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಮೆಮೊರಿಯನ್ನು ಬಳಸಲಾಗುವುದಿಲ್ಲ.

1