ಹೌಸ್ ರಾಬರ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


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

“ಹೌಸ್ ರಾಬರ್ II” ಸಮಸ್ಯೆಯಲ್ಲಿ, ದರೋಡೆಕೋರರು ವಿವಿಧ ಮನೆಗಳಿಂದ ಹಣವನ್ನು ದೋಚಲು ಬಯಸುತ್ತಾರೆ. ಮನೆಗಳಲ್ಲಿನ ಹಣವನ್ನು ಒಂದು ಶ್ರೇಣಿಯ ಮೂಲಕ ನಿರೂಪಿಸಲಾಗಿದೆ. ಈ ಕೆಳಗಿನ ಷರತ್ತುಗಳಿಗೆ ಅನುಗುಣವಾಗಿ ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಮಾಡಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕು:

  1. ಸತತ ಎರಡು ಮನೆಗಳನ್ನು ದರೋಡೆ ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ. ಅಂದರೆ, ನಮ್ಮ ಮೊತ್ತದಲ್ಲಿ ಸತತ ಎರಡು ಅಂಶಗಳನ್ನು ನಾವು ಸೇರಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ವೇಳೆ ದೆವ್ವದ ಕೂಸು ಫಲಿತಾಂಶಕ್ಕೆ ಅಂಶವನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆ, ನಂತರ (ನಾನು + 1)ನೇ ಮತ್ತು (i - 1)ನೇ ಅಂಶವನ್ನು ಹೊರಗಿಡಬೇಕು.
  2. ರಚನೆಯು ವೃತ್ತಾಕಾರವಾಗಿದೆ. ಆದ್ದರಿಂದ, ದಿ ಪ್ರಥಮ ಮತ್ತು ಕಳೆದ ಅಂಶವು ಪರಸ್ಪರ ಪಕ್ಕದಲ್ಲಿದೆ.

ಉದಾಹರಣೆ

1 5 4 2
7
4 5 6 8 3
13

ಅನುಸಂಧಾನ (ವಿವೇಚನಾರಹಿತ ಪಡೆ)

ರಚನೆಯಲ್ಲಿ ಸತತವಲ್ಲದ ಅಂಶಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಉತ್ಪಾದಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸಮಸ್ಯೆಯ ಅಗತ್ಯವಿದೆ. ಸತತವಲ್ಲದ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಪ್ರತಿಯೊಂದು ಅನುಕ್ರಮ ಸಂಯೋಜನೆಯನ್ನು ಪರಿಶೀಲಿಸಲು ನಾವು ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿಯನ್ನು ಚಲಾಯಿಸಬಹುದು. ಆದರೆ, ಸೂಚ್ಯಂಕಗಳು 1st ಮತ್ತು ಎನ್.ಟಿ. ವಾಸ್ತವವಾಗಿ ಪಕ್ಕದಲ್ಲಿದೆ. ಆದ್ದರಿಂದ, ನಮ್ಮ ಫಲಿತಾಂಶದಲ್ಲಿ ಇವೆರಡನ್ನೂ ಸೇರಿಸದಂತೆ ನಾವು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಬೇಕು. ಅಂತರ್ಬೋಧೆಯಿಂದ, ನಾವು ಸಬ್‌ರೇರ್‌ನಿಂದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಕಾಣಬಹುದು[1, ಎನ್ - 1] ಮತ್ತು ಸಬ್‌ರೇ[2, ಎನ್] ಪ್ರತ್ಯೇಕವಾಗಿ. ಈಗ, ಎರಡೂ ಸಬ್‌ರೇರ್‌ಗಳು ರೇಖೀಯವಾಗಿವೆ. ಫಲಿತಾಂಶವು ಎರಡು ಸಬ್‌ರೇ-ಮೊತ್ತಗಳಲ್ಲಿ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ.

ಈಗ, ಯಾವುದೇ ಸಾಮಾನ್ಯ ರೇಖೀಯ ರಚನೆಗೆ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸೋಣ. ವೃತ್ತಾಕಾರವು ರಚನೆಯಲ್ಲಿ ಇಲ್ಲ ಮತ್ತು ಅದು ಮೊದಲ ಅಂಶದಿಂದ ಪ್ರಾರಂಭವಾಗಿ ಕೊನೆಯದಾಗಿ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ ಎಂದು ನಾವು as ಹಿಸಿದಂತೆ, ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ಅಂಶವನ್ನು ಪಕ್ಕದಲ್ಲಿ ಪರಿಗಣಿಸುವುದನ್ನು ನಾವು ತೊಡೆದುಹಾಕಿದ್ದೇವೆ.

ನಾವು ಎರಡೂ ಮಾಡಬಹುದು ಎಂಬುದು ಈಗ ಸ್ಪಷ್ಟವಾಗಿದೆ:

  1. ಸೇರಿಸಿ ನಮ್ಮ ಮೊತ್ತದಲ್ಲಿನ ಯಾವುದೇ ಅಂಶ.
  2. ಹೊರಗಿಡಿ ಆ ಅಂಶ.

ಅಂತಹ ಸಂದರ್ಭದಲ್ಲಿ, ಸಂಭವನೀಯ ಎಲ್ಲ ಅನುಕ್ರಮಗಳಿಂದ ಉತ್ಪತ್ತಿಯಾಗುವ ಮೊತ್ತವನ್ನು ನಾವು ಕಾಣಬಹುದು ಸತತವಲ್ಲದ ಅಂಶಗಳು. ಸಾಧ್ಯವಿರುವ ಎಲ್ಲಾ ಸಂಯೋಜನೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನಾವು ಬಳಸಬಹುದು ಪುನರಾವರ್ತನೆ ಮತ್ತು ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್. ಪ್ರತಿ ಪುನರಾವರ್ತಿತ ಕರೆಯಲ್ಲಿ, ನಾವು ನಮ್ಮ ಫಲಿತಾಂಶದ ಮೊತ್ತದಲ್ಲಿ ಅಂಶವನ್ನು ಸೇರಿಸುತ್ತೇವೆ ಅಥವಾ ಅದನ್ನು ಹೊರಗಿಡುತ್ತೇವೆ. ಅದರ ಆಧಾರದ ಮೇಲೆ, ನಾವು ಸೂಚ್ಯಂಕದಲ್ಲಿ ಯಾವುದೇ ಅಂಶವನ್ನು ಆರಿಸಿದರೆ I, ನಂತರ ಮುಂದಿನ ಸೂಚ್ಯಂಕ ಇರಬೇಕು ನಾನು + 2, ನಾನು + 3.…. ಕೊನೆಯ ಅಂಶದವರೆಗೆ. ಅಂತೆಯೇ, ನಾವು ಸೂಚ್ಯಂಕದಲ್ಲಿ ಒಂದು ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿದರೆ I, ನಾವು ಸೂಚ್ಯಂಕದಲ್ಲಿ ಮುಂದಿನ ಪುನರಾವರ್ತನೆಯನ್ನು ಕರೆಯಬಹುದು ನಾನು + 1, ಅದರಿಂದ ಹುಟ್ಟುವ ಎಲ್ಲಾ ಸಾಧ್ಯತೆಗಳನ್ನು ಪರಿಶೀಲಿಸಲು. ಈ ರೀತಿಯಾಗಿ, ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಸೇರಿಸುವ ಮತ್ತು ಹೊರಗಿಡುವ ಸಾಧ್ಯತೆಗಳನ್ನು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅಲ್ಲದೆ, ಮೊತ್ತವನ್ನು ಒಳಗೊಂಡಿರುವ ಎಲ್ಲಾ ಅಂಶಗಳು ಸತತವಲ್ಲದ ನಾವು ಪ್ರತಿ ಪರ್ಯಾಯ ಸೂಚ್ಯಂಕಕ್ಕೆ ಹೋಗುವಾಗ.

ಕ್ರಮಾವಳಿ

  1. ರಚನೆಯು ಖಾಲಿಯಾಗಿದ್ದರೆ, ಹಿಂತಿರುಗಿ 0;
  2. ರಚನೆಯು ಒಂದು ಅಂಶವನ್ನು ಹೊಂದಿದ್ದರೆ
    • ನಾವು ರಚನೆಯನ್ನು ಎರಡು ಭಾಗಗಳಾಗಿ ವಿಭಜಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ಆದ್ದರಿಂದ, ರಚನೆಯ ಏಕೈಕ ಅಂಶವನ್ನು ಹಿಂತಿರುಗಿ
  3. ವೇರಿಯೇಬಲ್ ಅನ್ನು ನಿರ್ವಹಿಸಿ, max_sum_possible, ಇದು ಸಾಧ್ಯವಾದಷ್ಟು ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ
  4. ಪುನರಾವರ್ತಿತ ಕಾರ್ಯವನ್ನು ಕರೆ ಮಾಡಿ ಸಂಯೋಜನೆಗಳು () ಸಬ್‌ಅರೇ [1, ಎನ್ - 1] ಮತ್ತು [2, ಎನ್] ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ನಂತರದ ಪರಿಶೀಲನೆಗಾಗಿ
    • ಸಂಯೋಜನೆಗಳು ()  ಪ್ರತಿ ನಂತರದ ಮೊತ್ತವನ್ನು ಸಂಗ್ರಹಿಸಲು ನಿಯತಾಂಕವನ್ನು ಹೊಂದಿದೆ ಕರ್_ಸಮ್
    • ರಚನೆಯಿದ್ದರೆ ನಾವು ಕೊನೆಯ ಅಂಶವನ್ನು ದಾಟಿದ್ದರೆ, ಹಿಂತಿರುಗಿ.
    • ಈಗ, ನಾವು ಮಾಡಬಹುದಾದ ಎಲ್ಲ ಸಾಧ್ಯತೆಗಳನ್ನು ಪರಿಶೀಲಿಸೋಣ ಒಳಗೊಂಡು ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕ ಮೌಲ್ಯ
      • ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕ ಮೌಲ್ಯವನ್ನು ಸೇರಿಸಿ ಕರ್_ಸಮ್
      • ಪರ್ಯಾಯ ಸೂಚ್ಯಂಕದಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ ಇದರಿಂದ ನಾವು ಈ ಸೂಚ್ಯಂಕದಿಂದ ಸತತ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಹೋಗಬಹುದು
      • ಕಾಲ್ ಸಂಯೋಜನೆಗಳು () ಈ ಸೂಚ್ಯಂಕಗಳಲ್ಲಿ
    • ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಸೇರಿಸದಿದ್ದಾಗ ಸಾಧ್ಯತೆಯನ್ನು ಪರಿಶೀಲಿಸೋಣ
      • ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕ ಮೌಲ್ಯವನ್ನು ಕರ್_ಸಮ್‌ನಿಂದ ಕಳೆಯಿರಿ, ಇಲ್ಲಿ ನಾವು ಬ್ಯಾಕ್‌ಟ್ರಾಕ್ ನಮ್ಮ ಪರಿಹಾರ
      • ಕಾಲ್ ಸಂಯೋಜನೆಗಳು () ಮುಂದಿನ ಸೂಚ್ಯಂಕದಲ್ಲಿ, ನಾವು ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕವನ್ನು ಹೊರಗಿಟ್ಟಿದ್ದೇವೆ
    • ಪ್ರತಿ ಹಂತದಲ್ಲೂ, ನಾವು cur_sum> max_sum_possible ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ ಮತ್ತು ಅದನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ
  5. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಹೌಸ್ ರಾಬರ್ II ಅನ್ನು ಪರಿಹರಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನುಷ್ಠಾನ

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

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

void combinations(vector <int> &a , int &cur_sum , int idx , int &end , int &max_sum_possible)
{
    if(idx > end)
        return;


    cur_sum += a[idx];
    if(cur_sum > max_sum_possible)
        max_sum_possible = cur_sum;

    for(int i = idx + 2 ; i <= end ; i++)
        combinations(a , cur_sum , i , end , max_sum_possible);

    cur_sum -= a[idx];
    combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
    return;
}


int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    int max_sum_possible = 0 , cur_sum = 0 , end = n - 2;
    combinations(a , cur_sum , 0 , end , max_sum_possible);
    end++;
    combinations(a , cur_sum , 1 , end , max_sum_possible);

    return max_sum_possible;
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.lang.Math;


class MutableInt
{
    public int val;
    MutableInt(int x)
    {
        this.val = x;
    }
}


class House_Robber_II
{
    static void combinations(int[] a , int cur_sum , int idx , int end , MutableInt max_sum_possible)
    {
        if(idx > end)
            return;

        cur_sum += a[idx];
        if(cur_sum > max_sum_possible.val)
            max_sum_possible.val = cur_sum;

        for(int i = idx + 2 ; i <= end ; i++)
            combinations(a , cur_sum , i , end , max_sum_possible);

        cur_sum -= a[idx];
        combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
        return;
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        int cur_sum = 0 , end = n - 2;
        MutableInt max_sum_possible = new MutableInt(0);
        combinations(a , cur_sum , 0 , end , max_sum_possible);
        end++;
        combinations(a , cur_sum , 1 , end , max_sum_possible);

        return max_sum_possible.val;
    }
    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

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

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

O(N.2 ^ N.) ನಾವು ಸತತವಲ್ಲದ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಪ್ರತಿಯೊಂದು ಸಂಭವನೀಯತೆಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತೇವೆ.

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

ಒ (ಎನ್) ಪುನರಾವರ್ತಿತ ಸ್ಟಾಕ್ ಫ್ರೇಮ್‌ಗಳ ಕಾರಣ

ಅನುಸಂಧಾನ (ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್)

ಹಿಂದಿನ ವಿಧಾನದಲ್ಲಿ ನಾವು ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಚರ್ಚಿಸಬಹುದು

  • ಸೇರಿಸಿ ನಮ್ಮ ಮೊತ್ತದಲ್ಲಿನ ಅಂಶ.
  • ಹೊರಗಿಡಿ ಅಂಶ.

ಹೌಸ್ ರಾಬರ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಊಹಿಸುತ್ತವೆ ans [i, N] ನಾವು ಶ್ರೇಣಿಯಲ್ಲಿ ಪಡೆಯಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತವಾಗಿದೆ i ಗೆ N. ಈ ಫಲಿತಾಂಶವು ಉತ್ತರ [i + 2, N] ಮತ್ತು ಉತ್ತರ [i + 1, N] ಅನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ. ನಾವು ಪ್ರತಿಯೊಂದು ಶ್ರೇಣಿಯನ್ನು ಎ ಎಂದು ಪರಿಗಣಿಸಬಹುದು ರಾಜ್ಯ ಅಂದರೆ ಪ್ರತಿ ರಾಜ್ಯವು ಉಪ ರಾಜ್ಯಗಳ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿರುತ್ತದೆ. ಇತರ ಮೂಲ ರಾಜ್ಯ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ನಾವು ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ರಾಜ್ಯವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಪರಿಹರಿಸುವ ಸಾಧ್ಯತೆಯಿದೆ. ಇದು ಒಂದು ಆಪ್ಟಿಮಲ್ ಸಬ್ಸ್ಟ್ರಕ್ಚರ್. N ಗಾತ್ರದ ಒಂದು ಶ್ರೇಣಿಗೆ, ಎಲ್ಲಾ 'n' ಅಂಶಗಳಿಂದ ಪಡೆಯಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತವು ಈ ಎರಡು ಫಲಿತಾಂಶಗಳ ಗರಿಷ್ಠ ಎಂದು ನಾವು ತೀರ್ಮಾನಿಸಬಹುದು:

  • ತನಕ ಪಡೆದ ಅತ್ಯುತ್ತಮ ಫಲಿತಾಂಶ (ಎನ್ - 1) ಅಂಶಗಳು ಮತ್ತು Nth ಅಂಶವನ್ನು ಒಳಗೊಂಡಂತೆ
  • ತನಕ ಪಡೆದ ಅತ್ಯುತ್ತಮ ಫಲಿತಾಂಶ (ಎನ್ - 1) ಮತ್ತು Nth ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿ

ನಾವು ಅಂತಹ ಟೇಬಲ್ ಅನ್ನು ರಚಿಸಬಹುದು ಟೇಬಲ್ [i] ಸಬ್‌ರೇ [0, i] ಬಳಸಿ ಪಡೆಯಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ. ಆದರೆ, ಪ್ರತಿ ಸೂಚ್ಯಂಕಕ್ಕೆ ಎರಡು ಆಯ್ಕೆಗಳಿವೆ. ಆದ್ದರಿಂದ, ನಾವು ಪ್ರಕರಣಗಳಿಗಾಗಿ ಎರಡು ವಿಭಿನ್ನ ಫಲಿತಾಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಬೇಕಾಗಿದೆ: ಅಂಶವನ್ನು ಸೇರಿಸಿದಾಗ ಮತ್ತು ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿದಾಗ.

ಕ್ರಮಾವಳಿ

  1. ರಚನೆಯು ಖಾಲಿಯಾಗಿದ್ದರೆ, 0 ಹಿಂತಿರುಗಿ
  2. ರಚನೆಯು ಕೇವಲ ಒಂದು ಅಂಶವನ್ನು ಹೊಂದಿದ್ದರೆ, ಆ ಅಂಶವನ್ನು ಹಿಂತಿರುಗಿ
  3. ಕಾರ್ಯವನ್ನು ರಚಿಸಿ ರಾಬ್ಲೈನಿಯರ್ () ಅದು ರೇಖೀಯ ಶ್ರೇಣಿಯಲ್ಲಿ ಪಡೆಯಬಹುದಾದ ಗರಿಷ್ಠ ಮೊತ್ತವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ
  4. ರಾಬ್ಲೈನಿಯರ್ () ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ:
    1. ಒಳಗೊಂಡಿರುವ ಮತ್ತು ಹೊರತುಪಡಿಸಿದ ಎರಡು ಅಸ್ಥಿರಗಳನ್ನು ಪ್ರಾರಂಭಿಸಿ 0, ಇದು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಕ್ರಮವಾಗಿ ಸೇರಿಸುವ ಮತ್ತು ಹೊರಗಿಡುವ ಮೂಲಕ ಪಡೆಯಬಹುದಾದ ಗರಿಷ್ಠ ಫಲಿತಾಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸುತ್ತದೆ
    2. ಪ್ರತಿ ಮುಂದಿನ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ, ಒಳಗೊಂಡಿರುವ ಅಂಶವು ಪ್ರಸ್ತುತ ಅಂಶ + ಆಗುತ್ತದೆ ಹೊರಗಿಡಲಾಗಿದೆ ಹಿಂದಿನ ಅಂಶದ ಫಲಿತಾಂಶ
    3. ಹೊರತುಪಡಿಸಿದರೆ ಗರಿಷ್ಠವಾಗುತ್ತದೆ ಒಳಗೊಂಡಿತ್ತು ಮತ್ತು ಹೊರಗಿಡಲಾಗಿದೆ ಹಿಂದಿನ ಅಂಶದ ಫಲಿತಾಂಶಗಳು
  5. ಗರಿಷ್ಠ ರಾಬ್ಲೈನಿಯರ್ ಅನ್ನು ಹಿಂತಿರುಗಿ(1, ಎನ್ - 1) ಮತ್ತು ರಾಬ್ಲೈನಿಯರ್(2, ಎನ್)

ಹೌಸ್ ರಾಬರ್ II ಅನ್ನು ಪರಿಹರಿಸಲು ಅಲ್ಗಾರಿದಮ್ ಅನುಷ್ಠಾನ

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

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

int robLinear(int l , int r , vector <int> &a)
{
    int inc = 0 , exc = 0 , temp;

    for(int i = l ; i <= r ; i++)
    {
        temp = max(inc , exc);
        inc = exc + a[i];
        exc = temp;
    }
    return max(inc , exc);
}

int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    return max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.lang.Math;

class House_Robber_II
{
    static int robLinear(int l , int r , int[] a)
    {
        int inc = 0 , exc = 0 , temp;

        for(int i = l ; i <= r ; i++)
        {
            temp = Math.max(inc , exc);
            inc = exc + a[i];
            exc = temp;
        }
        return Math.max(inc , exc);
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        return Math.max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
    }

    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

ಹೌಸ್ ರಾಬರ್ II ಅನ್ನು ಪರಿಹರಿಸುವ ಸಂಕೀರ್ಣ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್), ನಾವು ಶ್ರೇಣಿಯನ್ನು 2 ಬಾರಿ ಸಂಚರಿಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ನಾವು O (2N) ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಮಾಡುತ್ತೇವೆ, ಅದು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

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

ಒ (1) ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ಬಳಸಲಾಗುತ್ತದೆ.