Untitled

 avatar
bruteCoder
java
7 months ago
580 B
1
Indexable
Never


class Solution {
    public int[] dp; 

    int findMaxSum(int arr[], int n) {
        // code here
        dp = new int[n];
        Arrays.fill(dp, -1);
        int ans = help(arr, 0, n, 0);
        return ans;
    }

    int help(int arr[], int i, int n, int curr) {
        if (i >= n) {
            return curr;
        }

        if (dp[i] != -1)
            return dp[i];

        // take
        int take = arr[i] + help(arr, i + 2, n, curr );

        // not take
        int notTake = help(arr, i + 1, n, curr);

        return dp[i] = Math.max(take, notTake);
    }
}
Leave a Comment