NC144：不相邻最大子序列和

解法1：动态规划

设置一个状态转移数组dp，dp[i]表示数组中前i个元素所能偷的最大金额是多少
状态转移表达式：
(1)对于当前的元素arr[i],如果偷，那么dp[i] = dp[i-2] + arr[i]
(2)如果不偷，那么dp[i] = dp[i-1]

    public long subsequence (int n, int[] array) {
        // write code here
        long[] dp=new long[n+1];// dp[i] 表示当前 i 个最大和
        dp[0]=0;
        dp[1]=array[0];
        for(int i=2;i<=n;i++){
            // 当前的最大值在前一个或者前两个和现在的和之间选择
            dp[i]=Math.max(dp[i-1],dp[i-2]+array[i-1]);
        }
        return dp[n];
    }

解法2：循环

逆序遍历

    public long subsequence (int n, int[] array) {
        // write code here
        long a=0,b=0,c=0;
        for(int i=n-1;i>=0;i--){
            c=Math.max(a,array[i]+b);
            b=a;
            a=c;
        }
        return c;
    }

正序遍历

    public long subsequence (int n, int[] array) {
        // write code here
        long a=0,b=0;
        //因为dp[i]只与dp[i-1]和dp[i-2]有关
        //所以分别定义两个数表示dp[i-1]和dp[i-2];
        for(int i=0;i<n;i++){
            long tmp=Math.max(b,a+array[i]);
            //相当于dp[i]=max(dp[i-1],dp[i-2]+array[i]);
            a=b;
            b=tmp;
        }
        return b;
    }