Coding Question 15

DP–>
import java.util.Arrays;

public class max_sum_nonadjacent {
public static void main(String[] args) {
int[] arr={3,2,5,10,7};
int[] t=new int[101];
Arrays.fill(t,-1);
System.out.println(solve(arr,0,t));

}
static int solve(int[] arr,int i,int[] t){
if(i>=arr.length){
return 0;
}
if(t[i]!=-1){
return t[i];
}
int steal=arr[i]+solve(arr,i+2,t);
int skip=solve(arr,i+1,t);
return t[i]=Math.max(steal,skip);
}
}