import java.util.* ; import java.io.*; import java.util.*; public class Solution { public static int maximumNonAdjacentSum(ArrayList<Integer> nums) { int n = nums.size(); // return s(nums , n-1 , new Integer[n]); int dp[] = new int[n]; dp[0] = nums.get(0); for(int i = 1 ;i < n ; i++){ int v = nums.get(i); int c1 = v , c2 = 0; if(i-2 >= 0) c1 = v + dp[i-2]; if(i-1 >= 0) c2 = 0 + dp[i-1]; dp[i] = Math.max(c1 ,c2); } return dp[n-1]; } public static int s(ArrayList<Integer> nums , int i , Integer[] dp){ int v = nums.get(i); if(i == 0){ return v; } if(dp[i] != null) return dp[i]; //minium value will be that element itself int c1 = v , c2 = 0; //take ,no take if(i-2 >= 0) c1 = v + s(nums , i-2 , dp); if(i-1 >= 0) c2 = 0 + s(nums ,i-1 , dp); return dp[i] = Math.max(c1 ,c2); } }