ಅತಿದೊಡ್ಡ ಭಾಗಿಸಬಹುದಾದ ಜೋಡಿಗಳ ಉಪವಿಭಾಗ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಗೂಗಲ್
ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮಠ

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

“ಅತಿದೊಡ್ಡ ಭಾಗಿಸಬಹುದಾದ ಜೋಡಿಗಳ ಉಪವಿಭಾಗ” ಸಮಸ್ಯೆ ನಿಮಗೆ n ವಿಭಿನ್ನ ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಉಪವಿಭಾಗದ ಪ್ರತಿಯೊಂದು ಜೋಡಿಯು ಸಣ್ಣ ಅಂಶಗಳಿಂದ ಭಾಗಿಸಬಹುದಾದ ದೊಡ್ಡ ಅಂಶವನ್ನು ಹೊಂದಿರುವ ದೊಡ್ಡದಾದ ಉದ್ದವನ್ನು ಹುಡುಕಿ.

ಉದಾಹರಣೆ

ಅತಿದೊಡ್ಡ ಭಾಗಿಸಬಹುದಾದ ಜೋಡಿಗಳ ಉಪವಿಭಾಗ

array = {1, 2, 4, 5, 8, 9, 16}
5

ವಿವರಣೆ

ಅತಿದೊಡ್ಡ ಉಪವಿಭಾಗವು 1, 2, 4, 8, 16 ಆಗಿದೆ, ಇದು ಸಮಸ್ಯೆಯಲ್ಲಿ ನಿರ್ದಿಷ್ಟಪಡಿಸಿದ ಸ್ಥಿತಿಯನ್ನು ಅನುಸರಿಸುತ್ತದೆ. ಈ ಉಪವಿಭಾಗದ ಉದ್ದ 5 ಆಗಿರುವುದರಿಂದ, ಉತ್ತರ 5 ಆಗಿದೆ.

ಅಪ್ರೋಚ್

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

ಆದ್ದರಿಂದ ಸಮಸ್ಯೆಯನ್ನು ಸಮರ್ಥವಾಗಿ ಪರಿಹರಿಸುವ ಸಲುವಾಗಿ. ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳಾಗಿ ಮುರಿಯಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಎಲ್ಲಾ ಜೋಡಿಗಳು ಸಣ್ಣ ಸಂಖ್ಯೆಯು ದೊಡ್ಡ ಸಂಖ್ಯೆಯನ್ನು ಭಾಗಿಸಬೇಕು ಎಂಬ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸಬೇಕು ಎಂದು ಸಮಸ್ಯೆ ಹೇಳುತ್ತದೆ. ಆದ್ದರಿಂದ, ನಾವು ಅದರ ಬಗ್ಗೆ ಯೋಚಿಸಿದರೆ ಎಲ್ಐಎಸ್ ಸಮಸ್ಯೆಯಂತೆಯೇ ಪರಿಹಾರವನ್ನು ನಾವು ಯೋಚಿಸಬಹುದು. ದೀರ್ಘಾವಧಿಯ ಹೆಚ್ಚುತ್ತಿರುವ ಪರಿಣಾಮ ಹೆಚ್ಚುತ್ತಿರುವ ಕ್ರಮದಲ್ಲಿರುವ ಅತಿದೊಡ್ಡ ಉಪವಿಭಾಗದ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ಹೇಳುತ್ತದೆ. ನಾವು ಇದೇ ರೀತಿಯದ್ದನ್ನು ಮಾಡಬಹುದು ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್. ನಾವು ಮೊದಲು ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುತ್ತೇವೆ. ನಂತರ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ, ನಾವು ಅದರ ಮೊದಲು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ನೋಡುತ್ತೇವೆ ಮತ್ತು ಯಾವುದೇ ಅಂಶಗಳು ಈ ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ವಿಭಜಿಸುತ್ತದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಯಾವುದೇ ಅಂಶವು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ವಿಭಜಿಸಿದರೆ, ನಾವು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಆ ಉಪವಿಭಾಗಕ್ಕೆ ಸೇರಿಸಬಹುದು ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ.

ಹೀಗೆ ನಾವು ಡಿಪಿ ವ್ಯೂಹವನ್ನು ರಚಿಸುತ್ತೇವೆ, ಅದರ ಇತ್ ಅಂಶವು ಅತಿದೊಡ್ಡ ಉಪವಿಭಾಗದ ಉದ್ದವನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಅದು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಅದರ ದೊಡ್ಡ ಅಂಶವಾಗಿ ಹೊಂದಿರುತ್ತದೆ. ಮತ್ತು ಉಪವಿಭಾಗವು ಸಮಸ್ಯೆಯ ಮೇಲೆ ಹೇರಿದ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುತ್ತದೆ.

ಕೋಡ್

ದೊಡ್ಡ ಭಾಗಿಸಬಹುದಾದ ಜೋಡಿಗಳ ಉಪವಿಭಾಗಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

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

int largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();
    if(n==0)return 0;
    sort(nums.begin(), nums.end());
    int dp[n], ans = INT_MIN;
    for(int i=0;i<n;i++){
        dp[i] = 1;
        for(int j=i-1;j>=0;j--)
            if(nums[i]%nums[j] == 0){
                if((dp[j]+1)>dp[i]){
                    dp[i] = dp[j]+1;
                    ans = max(ans, dp[i]);
                }
            }
    }
    return ans;
}

int main(){
  int n;cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
  int len = largestDivisibleSubset(v);
  cout<<len<<endl;
}
7
1 2 4 5 8 9 16
5

ಅತಿದೊಡ್ಡ ಭಾಗಿಸಬಹುದಾದ ಜೋಡಿಗಳ ಉಪವಿಭಾಗಕ್ಕಾಗಿ ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
  
  static int largestDivisibleSubset(ArrayList<Integer> nums) {
      int n = nums.size();
      if(n==0)return 0;
      Collections.sort(nums);
      int dp[] = new int[n];
      int ans = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          dp[i] = 1;
          for(int j=i-1;j>=0;j--)
              if(nums.get(i)%nums.get(j) == 0){
                  if((dp[j]+1)>dp[i]){
                      dp[i] = dp[j]+1;
                      ans = Math.max(ans, dp[i]);
                  }
              }
      }
      return ans;
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> v = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      v.add(a);
    }
    int len = largestDivisibleSubset(v);
    System.out.println(len);
  	}
}
7
1 2 4 5 8 9 16
5

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್ ^ 2), ಏಕೆಂದರೆ ಸಮಸ್ಯೆಯಲ್ಲಿ ನಾವು ಪ್ರಸ್ತುತ ಅಂಶದ ಮೊದಲು ಬಂದ ಎಲ್ಲ ಅಂಶಗಳ ಮೇಲೆ ಸಂಚರಿಸುತ್ತೇವೆ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.

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

ಒ (ಎನ್), ಮೌಲ್ಯಗಳನ್ನು ಡಿಪಿ ಟೇಬಲ್ ಆಗಿ ಸಂಗ್ರಹಿಸಲು ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಬಳಸಿದ್ದೇವೆ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.