maximum sum of subsequence-CodePudding

Given an integer array, find the maximum sum of subsequence where the subsequence contains no element at adjacent positions. Input: { 1, 2, 9, 4, 5, 0, 4, 11, 6 } Output: The maximum sum is 26

The maximum sum is formed by subsequence { 1, 9, 5, 11 }

My below code is working fine .helper2 method is same as findMaxSumSubsequence but with memoisation.Both these methods call themselves recursively exploring all subsets i.e take the element at ith pos or not take the element at ith position.

private int findMaxSumSubsequence(int[] arr ,int i ,boolean flag) {
        
        if( i>=arr.length)
            return 0;
        int incAns=0;
        if(!flag)
        {
        incAns=findMaxSumSubsequence(arr,i 1,true)   arr[i];
        }
        int exAns=findMaxSumSubsequence(arr,i 1,false) ;
        
       return Math.max(incAns, exAns);

But when i try to memoise the code I get the wrong answer for helper2(nums,0,false) //method call nums={1,2} after memoisation i get answer as 1 .Correct answer is 2.

int[] memo is initialised with -1 .

int[] memo = new int[101];
private  int helper2(int[] arr ,int i ,boolean flag) {
        
        if( i>=arr.length)
            return memo[i]=0;
            
             if(memo[i]!=-1)
            return memo[i];
            
        
            
        int incAns=0;
        if(!flag)
        {
        incAns=helper2(arr,i 1,true)   arr[i];
        }
        int exAns=helper2(arr,i 1,false) ;
            
           memo[i]= Math.max(incAns, exAns);
        
       return Math.max(incAns, exAns);

CodePudding user response：

You are missing the second memoization parameter 'flag', that's why you have a wrong answer, it should be:

int[][] memo = new int[101][2];

instead of

int[] memo = new int[101];

code:

    int[][] memo = new int[101][2];
    int [] arr;
    private  int helper2(int i ,boolean flag) {
        if (i >= arr.length)
            return 0;

        if (memo[i][flag? 1 : 0] != -1) return memo[i][flag ? 1 : 0];
        int incAns = 0;
        if (!flag) {
            incAns = helper2( i   1, true)   arr[i];
        }
        int exAns = helper2( i   1, false);

        return memo[i][flag? 1 : 0] = Math.max(incAns, exAns);
    }

    public static void main(String[] args)  {
        arr = new int[]{1, 2};
        for(int i = 0; i < 100; i  ) Arrays.fill(memo[i], -1);
        out.println(helper2(0, false));
    }

Also no need to add the array as a parameter in the recursive function because it's static and don't change, otherwise you will get Memory Limit Exceeded.