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);
	}
}