ಸಮೀಪದ ಅಂಶಗಳೊಂದಿಗೆ ದೊಡ್ಡ ಸಬ್‌ರೇರ್‌ನ ಉದ್ದ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಸಿಸ್ಕೋ ಕಾರಟ್ ಮೊನೊಟೈಪ್ ಪರಿಹಾರಗಳು ಪೇಟ್ಮ್ ಪೇಯು ಪಬ್ಲಿಸಿಸ್ ಸೇಪಿಯಂಟ್ ಎಸ್‌ಎಪಿ ಲ್ಯಾಬ್‌ಗಳು
ಅರೇ ಹ್ಯಾಶ್

“ಸಮೀಪವಿರುವ ಅಂಶಗಳೊಂದಿಗಿನ ಅತಿದೊಡ್ಡ ಸಬ್‌ಅರೇನ ಉದ್ದ” ಎಂಬ ಸಮಸ್ಯೆಯು ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಯಾವ ಅಂಶಗಳನ್ನು ಅನುಕ್ರಮವಾಗಿ ಜೋಡಿಸಬಹುದು (ನಿರಂತರ, ಆರೋಹಣ ಅಥವಾ ಅವರೋಹಣ) ಉದ್ದದ ಸಮೀಪದ ಉಪ-ರಚನೆಯ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ. ರಚನೆಯಲ್ಲಿನ ಸಂಖ್ಯೆಗಳು ಅನೇಕ ಬಾರಿ ಸಂಭವಿಸಬಹುದು.

ಉದಾಹರಣೆ

ಸಮೀಪದ ಅಂಶಗಳೊಂದಿಗೆ ದೊಡ್ಡ ಸಬ್‌ರೇರ್‌ನ ಉದ್ದ

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

ವಿವರಣೆ

0 ನೇ ಸೂಚ್ಯಂಕದಿಂದ 3 ನೇ ಸೂಚ್ಯಂಕಕ್ಕೆ ಪ್ರಾರಂಭವಾಗುವ ಸಂಖ್ಯೆಯು 10, 12, 13, 11 ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದನ್ನು 10, 11, 12, 13 ರೀತಿಯಲ್ಲಿ ಜೋಡಿಸಬಹುದು, ಅದರಲ್ಲಿ ಉದ್ದ 4 ಆಗುತ್ತದೆ.

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

ವಿವರಣೆ

1 ನೇ ಸೂಚ್ಯಂಕದಿಂದ 3 ನೇ ಸೂಚ್ಯಂಕದವರೆಗೆ ಪ್ರಾರಂಭವಾಗುವ ಸಂಖ್ಯೆಯು 1, 3, 2 ಸಂಖ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದನ್ನು 1, 2, 3 ರೀತಿಯಲ್ಲಿ ಜೋಡಿಸಬಹುದು, ಅದರಲ್ಲಿ ಉದ್ದವು 3 ಆಗುತ್ತದೆ.

ಕ್ರಮಾವಳಿ

  1. ಹೊಂದಿಸಿ ಗರಿಷ್ಟ ಉದ್ದ 1 ಗೆ.
  2. ಲೂಪ್ ತೆರೆಯಿರಿ, i = 0, ಆದರೆ ನಾನು <l -1,
    1. ಎ ಘೋಷಿಸಿ ಹೊಂದಿಸಿ ಮತ್ತು ಸೆಟ್ನಲ್ಲಿ arr [i] ಅನ್ನು ಸೇರಿಸಿ.
    2. ನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿಸಿ ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಮಿನ್ಲೆನ್ to arr [i].
    3. J = i + 1 ರಿಂದ ಪ್ರಾರಂಭಿಸಿ, j <l,
      1. ಸೆಟ್ arr [j] ನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ,
        1. ನಿಜವಾಗಿದ್ದರೆ, ಮುರಿಯಿರಿ.
        2. ಬೇರೆ,
          1. ಸೆಟ್‌ಗೆ ಆರ್ [ಜೆ] ಅನ್ನು ಸೇರಿಸಿ.
          2. ಮಿನ್ಲೆನ್ ಮತ್ತು ಅರ್ [ಜೆ] ನಡುವಿನ ಕನಿಷ್ಠವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದನ್ನು ಮಿಲೆನ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ.
          3. ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಆರ್ಆರ್ [ಜೆ] ನಡುವಿನ ಗರಿಷ್ಠತೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದನ್ನು ಮ್ಯಾಕ್ಸ್ಲೆನ್ಗೆ ಸಂಗ್ರಹಿಸಿ.
          4. ಮ್ಯಾಕ್ಸ್ಲೆನ್-ನಿಮಿಷ = = ಜೆ - ಐ ಎಂದು ಪರಿಶೀಲಿಸಿ
            1. ನಿಜವಾಗಿದ್ದರೆ ಮ್ಯಾಕ್ಸ್‌ಲೆಂಗ್ತ್ ಮತ್ತು ಮ್ಯಾಕ್ಸ್-ಮಿನ್ಲೆನ್ +1 ನಡುವಿನ ಗರಿಷ್ಠತೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದನ್ನು ಮ್ಯಾಕ್ಸ್‌ಲೆಂಗ್ತ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ.
  3. ಗರಿಷ್ಠ ಉದ್ದವನ್ನು ಹಿಂತಿರುಗಿ.

ವಿವರಣೆ

ಅನುಕ್ರಮದಲ್ಲಿ ಜೋಡಿಸಬಹುದಾದ ಕೆಲವು ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿರುವ ಅತಿ ಉದ್ದದ ಉಪ-ರಚನೆಯ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುವ ಪ್ರಶ್ನೆಯನ್ನು ನಮಗೆ ನೀಡಲಾಗಿದೆ. ಕೊಟ್ಟಿರುವ ರಚನೆಯು ನಕಲಿ ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿರುವ ಸಂದರ್ಭವಿರಬಹುದು. ನಾವು ಆ ಪ್ರಕರಣವನ್ನು ಸಹ ನಿರ್ವಹಿಸಬೇಕಾಗಿದೆ. ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು, ನಾವು a ಅನ್ನು ಬಳಸುತ್ತೇವೆ ಹೊಂದಿಸಿ ಮತ್ತು ನಕಲಿ ಅಂಶಗಳನ್ನು ನೋಡಿಕೊಳ್ಳುವ ನೆಸ್ಟೆಡ್ ಲೂಪ್.

ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಪರಿಗಣಿಸೋಣ:

ಉದಾಹರಣೆ

ಅರ್ [] = {10, 12, 13, 11, 8, 10}

ನಾವು ಲೂಪ್ ಅನ್ನು ತೆರೆದ ನಂತರ ಒಂದು ಸೆಟ್ ಅನ್ನು ಬಳಸುತ್ತೇವೆ ಮತ್ತು ಸಂಖ್ಯೆಯನ್ನು ಒಂದೊಂದಾಗಿ ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಮಿನ್ಲೆನ್ ಮೌಲ್ಯವನ್ನು ಅರ್ [i] ಗೆ ಹೊಂದಿಸುತ್ತೇವೆ. ನಂತರ ಪ್ರಸ್ತುತ ಅಂಶಕ್ಕಿಂತ ಒಂದು ಅಂಶದಿಂದ ಪ್ರಾರಂಭವಾಗುವ ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಅನ್ನು ತೆರೆಯಿರಿ, ಏಕೆಂದರೆ ನಾವು ಈಗಾಗಲೇ ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಸೆಟ್‌ಗೆ ಸೇರಿಸಿದ್ದೇವೆ. ಸೆಟ್ arr [j] ನ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ಅಂಶ ಕಂಡುಬಂದಲ್ಲಿ, ನಂತರ ಮುರಿಯಿರಿ. ಇಲ್ಲದಿದ್ದರೆ ಸೆಟ್‌ನಲ್ಲಿ ಅರ್ [ಜೆ] ಮೌಲ್ಯವನ್ನು ಸೇರಿಸಿ ಮತ್ತು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್ ಮತ್ತು ಅರ್ [ಜೆ] ನಡುವಿನ ಗರಿಷ್ಠತೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ, ಮತ್ತು ಮಿನ್ಲೆನ್ ಮತ್ತು ಅರ್ [ಜೆ] ನಡುವೆ ಕನಿಷ್ಠ ಮತ್ತು ಅದನ್ನು ಕ್ರಮವಾಗಿ ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಮಿನ್ಲೆನ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ. ಮ್ಯಾಕ್ಸ್ಲೆನ್-ನಿಮಿಷವು ಜಿ ಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ನಂತರ ಗರಿಷ್ಠ ಉದ್ದದ ಮೌಲ್ಯವನ್ನು ನವೀಕರಿಸಿ.

ಗರಿಷ್ಠ ಉದ್ದ = 1.

i = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, ಮೈಸೆಟ್ 12 ಹೊಂದಿದ್ದರೆ, ಅದು ಸುಳ್ಳು,

ಆದ್ದರಿಂದ ಮೈಸೆಟ್‌ನಲ್ಲಿ 12 ಅನ್ನು ಸೇರಿಸಿ ಮತ್ತು ಗರಿಷ್ಠ 12 ಮತ್ತು 10 ಅನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಕನಿಷ್ಠ 12 ಅನ್ನು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್‌ಗೆ ಮತ್ತು 10 ಅನ್ನು ಮಿನ್‌ಲೆನ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್-ಮಿನ್ಲೆನ್ ಜೆ - ಐಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ಆದರೆ ಅದು ಸುಳ್ಳು.

j = 2, ಮೈಸೆಟ್ 13 ಹೊಂದಿದ್ದರೆ, ಅದು ಸುಳ್ಳು,

ಆದ್ದರಿಂದ 13 ಅನ್ನು ಮೈಸೆಟ್‌ನಲ್ಲಿ ಸೇರಿಸಿ ಮತ್ತು ಗರಿಷ್ಠ 13 ಮತ್ತು 12 ಅನ್ನು ಹುಡುಕಿ ಮತ್ತು 13 ಅನ್ನು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್‌ಗೆ ಮತ್ತು 10 ಅನ್ನು ಮಿನ್‌ಲೆನ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್-ಮಿನ್ಲೆನ್ ಜೆಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ - ನಾನು ಸುಳ್ಳು.

j = 3, ಮೈಸೆಟ್ 11 ಹೊಂದಿದ್ದರೆ, ಅದು ಸುಳ್ಳು,

ಆದ್ದರಿಂದ 11 ಅನ್ನು ಮೈಸೆಟ್‌ಗೆ ಸೇರಿಸಿ ಮತ್ತು ಗರಿಷ್ಠ 11 ಮತ್ತು 10 ಅನ್ನು ಹುಡುಕಿ ಮತ್ತು 13 ಅನ್ನು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್‌ಗೆ ಮತ್ತು 10 ಅನ್ನು ಮಿನ್‌ಲೆನ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಮ್ಯಾಕ್ಸ್‌ಲೆನ್-ಮಿನ್ಲೆನ್ ಜೆಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ - ನಾನು ಈಗ ನಿಜ ಏಕೆಂದರೆ 13-10 3-0ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಗರಿಷ್ಠ ಗರಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠ-ಮಿನ್ಲೆನ್ + 1 ಗರಿಷ್ಠ (1, 13-10 + 1) ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ ಗರಿಷ್ಠ ಉದ್ದವನ್ನು ನವೀಕರಿಸಿ ಮತ್ತು ಅದು 4 ಮತ್ತು 4 ಎಂದು ತಿಳಿದುಬಂದಿದೆ ಮತ್ತು ಇದು ಗರಿಷ್ಠ ಉದ್ದದಲ್ಲಿ ಸಂಗ್ರಹಿಸಲ್ಪಟ್ಟಿದೆ ಮತ್ತು ಅದು ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತದೆ ಮತ್ತು ಇದು ಉಪ-ರಚನೆಯ ಉದ್ದಕ್ಕಿಂತ ಉದ್ದವನ್ನು ಕಂಡುಕೊಳ್ಳುವವರೆಗೆ ಹೊಂದಿಸಿ.

Put ಟ್ಪುಟ್: 4

ಕೋಡ್

ಸಮೀಪದ ಅಂಶಗಳೊಂದಿಗೆ ದೊಡ್ಡ ಸಬ್‌ರೇರ್‌ನ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

ಸಮೀಪದ ಅಂಶಗಳೊಂದಿಗೆ ಅತಿದೊಡ್ಡ ಸಬ್‌ರೇರ್‌ನ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

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

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

ಒ (ಎನ್2) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.