stickler thief

I would consider this problem as the tricky one which would have been easy. 

Literally, for no good reason I spent around 25 minutes thinking about a linear approach for this which didn't even exist, 

and I just can't understand why I didn't consider the fact that when we are taking the ... suppose 1st num of array, then we have to ignore the next but we are not bound to take the one in the 2nd position after this elem, we have lots of choices for that which makes this uncertain and that guides us to the Recursion + DP approach, or Tabulation( whatever you prefer ).

 

Well, maybe I need to spend more time with such kinds of probs cause these have never been my strong suite, but I am starting to sink these in, and maybe the approach is not so obvious to me but with the increase in the number of such types of probs, it's starting to make more and more sense, and the patterns are becoming clear.

This is the reason why it is important to spend time solving problems on our own, cause the matter is not the problems, it's us, and how we take these probs, what goes in our mind. We don't have to understand the problems we have to understand our mindset, and train it accordingly.

 Also when it doesn't work  ;)

            

 

For the logic part of this prob, to be dead simple, it's just that for every elem in array, there are 2 choices:

Either we take this elem, means we cannot take the next one so we make the function call for the +2 position elem, and make further decisions for that.

OR....

we ignore this elem and so we can just go to the next elem, and make decision for that.

Although I didn't get so as to why the Recursion + DP had a seg fault in Case 1110, it really sucked, but I don't understand it and assuming that it is probably the mistake from the GFG Test Cases side.

It was a fairly busy day considering that there was an assignment test today, or mid term whatever, which took exact 5 hours of my day. It's around 11:15 now, and I am gonna have to finish atleast 4 lectures( I'll try ) on React, then an article is left that's it. 

So gotta hurry up with those, peace ;)

Problem Statement:

Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. ith house has a[i] amount of money present in it.

Example 1:

Input:
n = 5
a[] = {6,5,5,7,4}
Output: 
15
Explanation: 
Maximum amount he can get by looting 1st, 3rd and 5th house. Which is 6+5+4=15.

Example 2:

Input:
n = 3
a[] = {1,5,3}
Output: 
5
Explanation: 
Loot only 2nd house and get maximum amount of 5.

Your Task:
Complete the functionFindMaxSum() which takes an array arr[] and n as input which returns the maximum money he can get following the rules.

Expected Time Complexity:O(N).
Expected Space Complexity:O(N).

Constraints:
1 ≤ n ≤ 105
1 ≤ a[i] ≤ 104

Code Implementation:

class Solution:  

   

    # def solve(self,a,n,ind,dp):

    #     if(ind>=n):

    #         return 0

       

    #     if(dp[ind]!=-1):

    #         return dp[ind]

           

    #     if(ind==n-1):

    #         # if we get to the last elem, then this is the best we got

    #         # means, if we ignore this(which will be giving 0) or we take this(a[n-1])

    #         return a[n-1]

       

    #     # either take this elem(then gotta skip the next elem and go to ind+2'th elem,

    #     # or just ignore it and go to the next one, for choosing again

    #     choice1=a[ind]+self.solve(a,n,ind+2,dp)

    #     choice2=self.solve(a,n,ind+1,dp)

       

    #     dp[ind]= max(choice1,choice2)

    #     return dp[ind]

       

    #Function to find the maximum money the thief can get.

    def FindMaxSum(self,a, n):

        # using the tabulation approach

        dp=[0]*n

        dp[0]=a[0]

       

        for i in range(1,n):

            choice1=a[i]

            choice2=dp[i-1]

            # if we have an elem 2 places behind, then we can have that wil a[i] too

            # cause that's not consecutive with i'th element

            if(i-2>=0):

                # this means the best answer of i-2 pos. elem. combined with i'th elem

                choice1+=dp[i-2]

           

            # the result for this i'th position will be the best choice b/w these 2

            dp[i]=max(choice1,choice2)

           

        return dp[n-1]

       

        ''' could have used the Recursion + DP approach too '''

        # for some unknown reason this methods is giving seg fault in 1110 TC

        # that makes no sense because seg fault doesn't just happend like that in

        # just 1 case, all boundations are fine and also there is no corner case

       

        # dp=[-1]*n

        # ans=self.solve(a,n,0,dp)

        # return ans