// Maximum Sum of Non-Adjacent Elements(Memoization)

// tc = O(n)

// sc = O(n) + O(n) --> stack space + extra dp array

import java.util.*;

public class dp {

    public static int func(int index, int arr[],int dp[])

    {

        if(index==0) return arr[index];

        if(index<0) return 0;

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

        int pick = func(index-2, arr,dp) + arr[index];

        int notpick = func(index-1, arr, dp) + 0;

        return dp[index] = Math.max(pick,notpick);

    }

    public static void main(String[] args) {

         int arr[] = {2,1,4,9};

         int n = 3; // or, n=arr.length

         int dp[] = new int[n+1]; // then n

         Arrays.fill(dp,-1);

         System.out.println(func(n,arr,dp));

    }

}