题解 | #不相邻取数#

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        long n=Long.parseLong(sc.nextLine());
        String[] arrstr=sc.nextLine().split(" ");
        
        long[] arr=new long[arrstr.length];
        
        for(int i=0;i<arrstr.length;i++){
            arr[i]=Long.parseLong(arrstr[i]);
        }
        long run=run(arr.length,arr);
        System.out.println(run);
    }
    public static long run(int n,long[] arr){
        if(arr==null||arr.length==0){
            return -1;
        }
        if(arr.length==1){
            return arr[0];
        }
        if(arr.length==2){
            return Math.max(arr[0],arr[1]);
        }
        //创建dp数组
        long[] dp=new long[n];
        dp[0]=arr[0];
        dp[1]=Math.max(arr[0],arr[1]);
        //状态转移
        for(int i=2;i<arr.length;i++){
            long a=dp[i-2]+arr[i];
            long b=dp[i-1];
            dp[i]=Math.max(a,b);
        }
        return dp[n-1];
    }
}