思路

本题是个动态规划问题，所以按照动态规划的解题步骤来思考问题

1.确定状态

本题无非就是要找到一些不相邻数的数，使得它们的和最大。状态可以很自然的想到可以用元素和来表示。

2.确定dp数组含义

dp[i]表示以arr[i]为结尾元素时的最大值

3.确定选择

针对第i个元素arr[i]，要从dp[0]~dp[i-2] (因为不相邻，所以必须从i之前的两位开始)选择最大的一个值，dp[i] = arr[i]+max{dp[0],dp[1]...dp[i-2]},由于arr[i]>0，所以没必要从0开始，dp[i]只与dp[i-2]和dp[i-3]有关

4.确定base case

dp[0] = arr[0],dp[1]=arr[1]，dp[2]=arr[0]+arr[2]

5.确定状态转移方程

6.代码示例

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        for(int i=0;i<n;i++){
            arr[i] = in.nextLong();
        }
        if(n==1){
            System.out.println(arr[0]);
        }
        if(n==2){
            System.out.println(arr[1]>arr[0]?arr[1]:arr[0]);
        }
        long[] dp = new long[n];
        dp[0] = arr[0];
        dp[1] = arr[1];
        dp[2] = arr[0]+arr[2];
        for(int i=3;i<dp.length;i++){        
            dp[i] = arr[i]+(dp[i-2]>dp[i-3]?dp[i-2]:dp[i-3]);
        }     
        System.out.println(dp[n-1]>dp[n-2]?dp[n-1]:dp[n-2]);
    }
}